跳至主要內容

LeetCode 321. 拼接最大数——分治+单调栈合并两数组最大子序列

老张2026/4/30大约 8 分钟

LeetCode 321. 拼接最大数——分治+单调栈合并两数组最大子序列

适读人群：Java 中高级工程师、备战大厂面试的同学 | 阅读时长：约25分钟 | 难度：困难

开篇故事

这是这个单调栈系列里第一道真正的「困难」题。它是上一篇「移掉K位数字」的硬核升级版，把从一个数组里取子序列，变成了从两个数组里各取一部分然后合并。

我刚做这道题的时候，思路方向是对的：分治，枚举从第一个数组取 i 个、第二个数组取 k-i 个，各自用单调栈取最大子序列，然后合并两个序列取最大。但卡在「合并两个序列取最大」这个步骤上。

合并的时候，不是简单的归并排序，因为数字相等时需要看后续的更大，这是一个比较微妙的「字典序比较」问题。写了好几个错误的比较函数才理清楚。

这道题是对前几篇内容的一次综合考核，建议先把 316 和 402 熟练之后再来挑战。

一、题目解析

题目描述：

给你两个整数数组 nums1 和 nums2，它们的长度分别为 m 和 n。从两个数组中选取 k 个数字，构造最大数，要求：

  • 从 nums1 中选取的数字保持原始相对顺序
  • 从 nums2 中选取的数字保持原始相对顺序
  • 两者合并后组成 k 位最大数

返回这 k 个数字组成的最大数（以数组形式表示）。

示例：

输入：nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
输出：[9,8,6,5,3]

输入：nums1 = [6,7], nums2 = [6,0,4], k = 5
输出：[6,7,6,0,4]

约束：

  • m + n >= k
  • 0 <= i <= min(m, k)

二、解法一：暴力枚举所有分割

思路分析

枚举从 nums1 取 i 个（i 从 max(0, k-n) 到 min(k, m)），分别得到两个子序列，合并取最大。

这里先不优化各步骤，用最朴素的方式：

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        int[] result = new int[k];
        
        for (int i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
            // 从 nums1 取 i 个，从 nums2 取 k-i 个
            int[] sub1 = maxSubsequence(nums1, i);
            int[] sub2 = maxSubsequence(nums2, k - i);
            int[] merged = merge(sub1, sub2);
            // 如果 merged 更大，更新结果
            if (compare(merged, 0, result, 0) > 0) {
                result = merged;
            }
        }
        
        return result;
    }
    
    // 从 nums 中选出 k 个元素，保持原顺序，使结果最大（单调栈）
    private int[] maxSubsequence(int[] nums, int k) {
        int n = nums.length;
        int[] stack = new int[n];
        int top = -1;
        int drop = n - k; // 可以删掉的数量
        
        for (int num : nums) {
            while (top >= 0 && stack[top] < num && drop > 0) {
                top--;
                drop--;
            }
            stack[++top] = num;
        }
        return Arrays.copyOf(stack, k);
    }
    
    // 合并两个数组，取字典序最大
    private int[] merge(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] result = new int[m + n];
        int i = 0, j = 0, idx = 0;
        
        while (i < m || j < n) {
            if (compare(nums1, i, nums2, j) >= 0) {
                result[idx++] = nums1[i++];
            } else {
                result[idx++] = nums2[j++];
            }
        }
        return result;
    }
    
    // 比较从 i/j 开始的数组字典序大小
    private int compare(int[] nums1, int i, int[] nums2, int j) {
        int m = nums1.length, n = nums2.length;
        while (i < m && j < n) {
            if (nums1[i] != nums2[j]) return nums1[i] - nums2[j];
            i++;
            j++;
        }
        return (m - i) - (n - j); // 剩余长度更长的更大
    }
}

复杂度分析

  • 时间复杂度：O(k × (m+n)²)。枚举 k 种分割，每种合并操作 O((m+n)²)（比较函数最坏 O(m+n)）。
  • 空间复杂度：O(k)。

三、解法二：优化合并步骤

这个解法和最优解思路完全一致，区别在于合并时的比较函数优化。核心算法不变，单独把比较函数作为一个解法阶段说明：

最朴素的合并是每次取更大的头部，相等时线性比较后续，最坏 O((m+n)²)。用后缀数组可以优化到 O(m+n)，但工程实现复杂。

对于本题而言，由于 m+n <= 500（约束范围内），简单实现已经够用。

四、解法三（最优）：分治 + 单调栈 + 字典序合并

这里把整个解题流程拆开，清晰展示三个核心步骤：

步骤一：单调递减栈取最大子序列

从一个数组中取 k 个保持相对顺序的最大子序列，等价于「删掉 n-k 个数字使结果最大」——402 题的变体（这次是找最大而非最小，用单调递减栈）。

步骤二：比较两个子数组的字典序

合并时，当两个头部相同，不能随意选，必须比较后续字典序，选字典序更大的那个。

步骤三：归并合并两个子序列

完整代码

import java.util.*;

class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        int[] result = new int[k];
        
        // 枚举从 nums1 取 i 个
        for (int i = Math.max(0, k - n); i <= Math.min(k, m); i++) {
            int[] sub1 = maxSubsequence(nums1, i);
            int[] sub2 = maxSubsequence(nums2, k - i);
            int[] candidate = merge(sub1, sub2);
            if (compare(candidate, 0, result, 0) > 0) {
                result = candidate;
            }
        }
        
        return result;
    }
    
    /**
     * 从 nums 中选出 len 个数字保持原始顺序，使组成的数字最大
     * 思路：单调递减栈，可以删掉 drop = nums.length - len 个数字
     */
    private int[] maxSubsequence(int[] nums, int len) {
        if (len == 0) return new int[0];
        int n = nums.length;
        int[] stack = new int[n];
        int top = -1;
        int drop = n - len; // 允许删除的次数
        
        for (int num : nums) {
            // 当前数比栈顶大，且还可以删，就弹出栈顶（删除较小的）
            while (top >= 0 && stack[top] < num && drop > 0) {
                top--;
                drop--;
            }
            stack[++top] = num;
        }
        
        // 取前 len 个元素（如果 drop 没有用完，栈顶是较小的，自然截取前 len 个）
        return Arrays.copyOf(stack, len);
    }
    
    /**
     * 合并两个数组，每次选字典序更大的头部
     */
    private int[] merge(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        if (m == 0) return nums2;
        if (n == 0) return nums1;
        
        int[] result = new int[m + n];
        int i = 0, j = 0, idx = 0;
        
        while (i < m || j < n) {
            // 比较两个序列的当前后缀字典序
            if (compare(nums1, i, nums2, j) >= 0) {
                result[idx++] = nums1[i++];
            } else {
                result[idx++] = nums2[j++];
            }
        }
        
        return result;
    }
    
    /**
     * 比较两个数组从指定位置开始的字典序
     * 返回正数表示 nums1[i:] > nums2[j:]，负数反之，0相等
     */
    private int compare(int[] nums1, int i, int[] nums2, int j) {
        int m = nums1.length, n = nums2.length;
        while (i < m && j < n) {
            if (nums1[i] != nums2[j]) {
                return nums1[i] - nums2[j];
            }
            i++;
            j++;
        }
        // 其中一个已经到末尾，剩余元素更多的字典序更大
        return (m - i) - (n - j);
    }
}

手动模拟

以 nums1=[3,4,6,5], nums2=[9,1,2,5,8,3], k=5 为例，枚举 i=0..4：

  • i=0：sub1=[], sub2=maxSub(nums2,5)=[9,5,8,3] 不对，让我重新计算
    • maxSubsequence([9,1,2,5,8,3], 5)：drop=1
      • 9入，1入，2>1弹1(drop=0)，2入，5>2弹2但drop=0，5入，8>5弹5但drop=0，8入，3入
      • 栈=[9,2,5,8,3]... 等等

让我重新模拟：drop=6-5=1

  • 9: 入栈=[9]

  • 1: 1<9 不弹，入=[9,1]

  • 2: 2>1 且drop=1，弹1(drop=0)，2>9? 不，入=[9,2]

  • 5: 5>2 但drop=0，入=[9,2,5]

  • 8: 8>5 但drop=0，入=[9,2,5,8]

  • 3: 3<8，入=[9,2,5,8,3] 结果：[9,2,5,8,3]

  • i=2：sub1=maxSub([3,4,6,5],2)=[6,5], sub2=maxSub([9,1,2,5,8,3],3)=[9,8,3] 合并[6,5]和[9,8,3]：9>6取9，8>6取8，6>3取6，5>3取5，3结束→[9,8,6,5,3]

  • 最终答案：[9,8,6,5,3]，正确！

复杂度分析

  • 时间复杂度：O(k × (m+n))。枚举 k+1 种分割，每次 maxSubsequence O(m) 或 O(n)，merge O(m+n)，compare O(m+n)，总体 O(k(m+n))。
  • 空间复杂度：O(m+n)。

五、举一反三

这道题综合了单调栈和合并排序两个技巧，在以下场景有变体：

  • 多数组版本：从 p 个数组各取若干个，总共 k 个，合并最大。可以递归处理，两两合并。
  • 最小数版本：从两个数组各取部分合并成最小数，只需要把单调递减栈换成单调递增栈，合并时选较小的。

六、踩坑实录

坑一：compare 函数的边界：剩余长度的处理

当两个序列有一个先到末尾时，剩余长度更长的字典序更大。比如 [5] vs [5,3]，后者从第5后面跟了个3，所以后者更大（53 > 5）。

return (m - i) - (n - j); // 正数表示nums1剩余更多，字典序更大

这里容易写成 return 0（认为相等），会导致合并时选择不优化的序列，输出错误结果。

坑二：maxSubsequence 中截取前 len 个而非全部

单调栈结束后，top+1 是栈的大小，可能大于 len（因为 drop 没有用完时多入了些元素）。必须截取前 len 个，不能全取。

return Arrays.copyOf(stack, len); // 取前 len 个，不是 top+1

坑三：枚举 i 的范围边界

从 nums1 取 i 个，i 的范围是 [max(0, k-n), min(k, m)]：

  • 最少取 k-n（因为 nums2 最多提供 n 个）
  • 最多取 min(k, m)（不超过 k 且不超过 nums1 的长度）

如果范围搞错，会产生越界或漏掉有效情况。

七、总结

321 是这个单调栈系列里综合性最强的题，融合了：

  1. 单调栈取最优子序列（402 的核心）
  2. 字典序比较（合并时的关键）
  3. 分治枚举（从两个数组各取多少的拆分思路）

这三个部分任何一个写错都会导致最终答案错误，是很好的综合训练题目。

编辑此页
最近更新:
贡献者: xiaozhangge