LeetCode 321. 拼接最大数

约 8 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 5-10 字节 虾皮
标签
数组 双指针 栈 贪心 单调栈

题目描述

✅ 321. 拼接最大数

image-20260928235311630

image-20260928235311632

题意分析

从两个数字数组中一共选出 k 个数字，按某种方式交错拼成最大的数，返回长度为 k 的数字数组。同一来源数组中被选数字的相对顺序必须保持，但可以跳过不选的数字；两个来源之间没有固定的先后关系。

因此不能把所有数字合在一起排序，也不能要求每个来源选出的部分连续。所有候选长度都为 k，比较大小等价于比较字典序：从左到右找到第一处不同，那里较大的数字就决定整个候选更大。

解法：枚举分配 + 单调栈 + 后缀贪心归并

核心思路

[!blue]

先枚举两个来源各取多少个。设第一数组取 take1 个，第二数组就取 k - take1 个。为保证两边都取够且不超长，take1 的范围是 max(0, k - nums2.length) 到 min(k, nums1.length)，这样覆盖全部合法分配。

固定分配后，每个来源可以独立选择该长度的最大子序列。理由是：固定另一来源和交错位置不变，把某一侧换成字典序更大的同长度子序列，会在该侧第一次不同的输出位置使总结果更大，不会影响此前字符。因此较小的同长度子序列不可能比最大子序列更有利。

从长度为 N 的数组选 length 个数，相当于允许删除 drop = N - length 个。用栈保存已选前缀，遇到更大的新数字时，只要还可删除，就弹出较小栈顶，让更大数字靠前。这个替换改善了第一处不同的位置，而删除额度保证仍能留够目标长度；数字相等时保留较早的那个即可。

栈未满时加入当前数字，已满时跳过它，并同样消耗一个删除额度。弹出旧值和跳过新值都是删除，必须统一计数。额度用完后，即使后面出现更大数字，也不能继续弹出，否则可能凑不够长度；因此最终子序列不一定整体单调。

两条最大子序列还需要合并。若当前数字不同，先取较大者；若相同，必须比较完整的剩余后缀，直到第一处不同，选择后续字典序更大的一侧。前面的相同数字暂时无法拉开差距，提前推进较大的后缀，才能更早把它较大的后续数字放入结果。只看当前位并任意打破平局，可能让较小的后继挡在更大后继之前。

后缀比较时，若一侧已经耗尽，另一侧非空后缀更大；完全相同则任选一侧。每次只取所选后缀的第一个数字，然后重新比较新的两个后缀，保证两侧原有顺序不变。最后把不同分配得到的候选互相比字典序，保留最大结果。

解题步骤

  1. 计算第一数组可取数量的合法上下界，逐个枚举。
  2. 对每种分配，分别用删除额度控制的栈选出两边定长最大子序列。
  3. 用两个下标指向子序列开头，每次比较剩余后缀，取较大后缀的首位加入候选。
  4. 某一侧耗尽后，继续取另一侧，直到候选长度为 k。
  5. 将候选与历史最好结果按字典序比较，枚举全部分配后返回最优数组。

代码实现

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        // 取数分配必须让两侧都不超过自身长度，枚举覆盖全部合法分配。
        int lower = Math.max(0, k - nums2.length);
        int upper = Math.min(k, nums1.length);
        int[] best = new int[k];

        for (int take1 = lower; take1 <= upper; take1++) {
            int[] part1 = maxSubsequence(nums1, take1);
            int[] part2 = maxSubsequence(nums2, k - take1);
            int[] candidate = merge(part1, part2);

            if (greater(candidate, 0, best, 0)) {
                best = candidate;
            }
        }

        return best;
    }

    private int[] maxSubsequence(int[] nums, int length) {
        int[] stack = new int[length];
        int top = 0;
        // 删除额度保证最终能留够目标长度，额度耗尽后不能再弹出。
        int drop = nums.length - length;

        for (int num : nums) {
            while (top > 0 && drop > 0 && stack[top - 1] < num) {
                top--;
                drop--;
            }

            // 栈满后跳过当前值也消耗一次删除额度，不能把额度留给后面重复删除。
            if (top < length) {
                stack[top++] = num;
            } else {
                drop--;
            }
        }

        return stack;
    }

    private int[] merge(int[] nums1, int[] nums2) {
        int[] merged = new int[nums1.length + nums2.length];
        int index1 = 0;
        int index2 = 0;

        for (int i = 0; i < merged.length; i++) {
            // 首位相同时继续比较整个剩余后缀，选择字典序更大的一侧。
            if (greater(nums1, index1, nums2, index2)) {
                merged[i] = nums1[index1++];
            } else {
                merged[i] = nums2[index2++];
            }
        }

        return merged;
    }

    // 完全相等也返回真，只决定相同候选的取用顺序，不影响最终最大值。
    private boolean greater(int[] nums1, int index1, int[] nums2, int index2) {
        while (index1 < nums1.length && index2 < nums2.length && nums1[index1] == nums2[index2]) {
            index1++;
            index2++;
        }

        return index2 == nums2.length || (index1 < nums1.length && nums1[index1] > nums2[index2]);
    }
}

func maxNumber(nums1 []int, nums2 []int, k int) []int {
    // 取数分配必须让两侧都不超过自身长度，枚举覆盖全部合法分配。
    lower := 0
    if k-len(nums2) > lower {
        lower = k - len(nums2)
    }
    upper := k
    if len(nums1) < upper {
        upper = len(nums1)
    }

    best := make([]int, k)
    for take1 := lower; take1 <= upper; take1++ {
        part1 := maxSubsequence(nums1, take1)
        part2 := maxSubsequence(nums2, k-take1)
        candidate := mergeMax(part1, part2)
        if greaterSeq(candidate, 0, best, 0) {
            best = candidate
        }
    }
    return best
}

func maxSubsequence(nums []int, length int) []int {
    stack := make([]int, 0, length)
    // 删除额度保证最终能留够目标长度，额度耗尽后不能再弹出。
    drop := len(nums) - length

    for _, num := range nums {
        for len(stack) > 0 && drop > 0 &&
            stack[len(stack)-1] < num {
            stack = stack[:len(stack)-1]
            drop--
        }
        // 栈满后跳过当前值也消耗一次删除额度，不能把额度留给后面重复删除。
        if len(stack) < length {
            stack = append(stack, num)
        } else {
            drop--
        }
    }
    return stack
}

func mergeMax(nums1 []int, nums2 []int) []int {
    merged := make([]int, len(nums1)+len(nums2))
    index1, index2 := 0, 0

    for i := range merged {
        // 首位相同时继续比较整个剩余后缀，选择字典序更大的一侧。
        if greaterSeq(nums1, index1, nums2, index2) {
            merged[i] = nums1[index1]
            index1++
        } else {
            merged[i] = nums2[index2]
            index2++
        }
    }
    return merged
}

// 完全相等也返回真，只决定相同候选的取用顺序，不影响最终最大值。
func greaterSeq(nums1 []int, index1 int, nums2 []int, index2 int) bool {
    for index1 < len(nums1) && index2 < len(nums2) &&
        nums1[index1] == nums2[index2] {
        index1++
        index2++
    }
    return index2 == len(nums2) ||
        (index1 < len(nums1) && nums1[index1] > nums2[index2])
}

复杂度分析

设两个输入长度为 m、n，合法分配数量为 A，且 A <= k + 1。

  • 时间复杂度：$O(A(m + n + k^2))$。每种分配的两次子序列选择为 $O(m + n)$，因为每个数字最多入栈、出栈各一次；归并 k 位时，每次比较剩余后缀最坏检查 $O(k)$ 个数字，因此归并最坏为 $O(k^2)$。
  • 空间复杂度：$O(k)$，两条子序列总长为 k，候选与历史最优也都长 k，只同时保存常数份候选，不保留所有分配结果。

关键点总结

[!green]

  • 枚举数量分配解决跨来源选择，单边最大子序列解决各自保序，后缀归并解决交错顺序。
  • 删除额度同时约束弹栈和跳过，既让较大数字靠前，又保证最终长度。
  • 相等首位不能决定归并方向，比较完整后缀后也只消费一位。

易错点总结

[!yellow]

  • 无条件枚举 0..k，会出现某一来源需要取出超过自身长度的数字；应先限制分配范围。
  • 为了更大的数字无限弹栈，会丢掉必须保留的位置，最终不足指定长度。
  • 栈满后跳过当前数却不扣删除额度，会让后面继续使用已经花掉的额度。
  • 首位相等时固定选一侧，会忽略更靠后的首次差异，得到较小的候选。
  • 将已经耗尽的后缀判为更大，会在归并中访问越界；非空后缀应优先。
  • 比较过程中找到差异后，一次性复制所选一侧的全部剩余数字，会错过与另一侧重新交错的机会。
  • 只尝试某一种取数比例，不能覆盖最优答案可能采用的另一种分配。

相似题目

题目 难度 关联与区别
402. 移掉 K 位数字 中等 同样从序列中删掉不利元素得到固定长度最优子序列，本题取最大并合并两个来源。
1754. 构造字典序最大的合并字符串 中等 合并时同样需要比较剩余后缀而非只比较当前字符，否则相同首字符会导致选错。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/17324701
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！