LeetCode 321. 拼接最大数

2026-05-21 HGNULB 约 8 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 321. 拼接最大数

题意分析

给定两个由一位数字构成的数组，要从它们中一共挑出 $k$ 个数字拼成一个长度为 $k$ 的序列，使这个序列在字典序意义下最大。约束是每个数组内部被选中的数字必须保持原有先后顺序，但两个数组的数字可以任意交错。

「保持相对顺序」这几个字说明从单个数组里挑出来的是子序列而非子集，位置不能重排；「可以交错」说明最终答案是两个子序列的一次归并。两条合起来意味着答案的形态被限定得很死：先决定从第一个数组取几个、从第二个取几个，再决定各自取哪几个，最后决定交错的方式。

由于每个元素都是 $0$ 到 $9$ 的一位数且两个候选序列等长，比较字典序等价于比较把它们当成数字时的大小，逐位比较即可，不必担心位数不同带来的干扰。

数据范围里两个数组长度都不超过 $500$，$k$ 不超过两者长度之和，这个规模明确允许一个带三重代价的枚举：外层可以枚举 $O(k)$ 种分配方式，内层再花线性甚至平方的代价，总量仍然可以接受。

边界情形有几类：某个数组一个都不取，此时它贡献空序列；$k$ 恰好等于两数组长度之和，此时两边都必须全取，没有挑选余地；数字大量重复，比如两个数组里全是同一个数字，这时归并阶段的比较会退化成「一直相等」，必须有明确的定夺规则；以及某个数组本身为空。

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

核心思路

最终答案由两边各取多少、每边取哪些、两段如何交错三个决策组成。先枚举从 nums1 取 take1 个，那么 nums2 必须取 k - take1 个；对每种分配，问题拆成两个独立子问题。

固定长度的最大子序列：设数组长度为 $n$、目标长度为 $t$，允许删除 drop = n - t 个元素。顺序扫描，用单调栈保存答案；当栈顶比当前数字小且仍有删除额度时，弹出栈顶。把更大的数字放到更靠前的位置一定能增大字典序，drop 则保证最后仍能凑够 $t$ 位。

两个子序列的最大归并：每步应选择剩余后缀中字典序更大的一侧。首位不同时直接选较大数字；首位相同时必须继续比较后缀，因为第一处不同的位置才决定整体大小。例如 [6,7] 与 [6,0] 应先取第一侧的 6，不能固定在相等时选某一数组。

对固定分配，最大子序列和最大归并分别保证局部最优；枚举覆盖所有合法分配，因此所有候选中的最大值就是全局答案。

解题步骤

枚举 take1，范围为 max(0, k - nums2.length) 到 min(k, nums1.length)。

分别用单调栈求两数组的定长最大子序列。

用后缀比较贪心归并两个子序列，得到长度为 $k$ 的候选。

将候选与当前最优答案按字典序比较并更新。

枚举结束后返回最优答案。

单调栈中的弹出条件必须同时满足“栈顶更小”和“还有删除额度”；数字相等时保留靠前者即可。归并时若一侧耗尽，另一侧后缀自然更大。

代码实现

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$。合法分配至多 $k+1$ 种。

时间复杂度：$O(k(m+n+k^2))$。每种分配求子序列需要 $O(m+n)$；归并 $k$ 位时，每次后缀比较最坏扫描 $O(k)$，因此为 $O(k^2)$。

空间复杂度：$O(k)$，两个子序列、候选和最优答案的总长度都与 $k$ 同阶；不计返回结果仍为 $O(k)$。

关键点总结

枚举“各取多少”后，选子序列与归并两个决策才能独立求最优。

定长最大子序列使用删除配额控制单调栈，不能为了更大数字无限弹栈。

归并比较的是完整剩余后缀，而不是只比较当前数字。

字典序由第一处不同决定；一侧先耗尽时，非空后缀更大。

这是困难题，面试时应先讲三层拆分，再分别证明单调栈和后缀贪心。

易错点总结

枚举范围固定写成 0...k：可能要求某个数组取出超过自身长度的元素。

栈满后丢弃当前数字却不减少 drop：后面会错误地继续弹栈。

相等首位时固定选某一侧：如 [6,7] 与 [6,0] 会得到更小结果。

后缀比较把空后缀判为更大：归并时可能访问已经耗尽的数组。

只保留某一种分配：最优答案可能来自另一种取数比例。

相似题目

题目	难度	考察点
402. 移掉 K 位数字	中等	只有一个序列且目标是字典序最小，是本题单调栈模板的最简形态
1673. 找出最具竞争力的子序列	中等	同为定长最小子序列，直接对应本题的单侧子问题，没有枚举与归并
316. 去除重复字母	中等	单调栈之外还要保证每个字符恰好出现一次，弹栈条件多了「后面是否还有」
179. 最大数	中等	同样追求拼接后最大，但元素可任意重排，靠自定义比较器排序而非子序列
88. 合并两个有序数组	简单	归并的基础形态，比较规则只看单个元素，不涉及后缀定夺
738. 单调递增的数字	中等	同为逐位贪心构造数字，但约束是结果本身单调且不超过给定上界