Article / 文章
LeetCode 第321题：拼接最大数
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
📖 文章摘要
本文详细解析LeetCode第321题“拼接最大数”，这是一道贪心算法和单调栈的问题。文章提供了基于单调栈和归并的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升贪心算法和单调栈应用能力的程序员。
核心知识点： 贪心算法、单调栈、归并
难度等级： 困难
推荐人群： 具有一定算法基础，想要提升复杂问题解决能力的程序员
题目描述
给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
示例
示例 1：
输入：nums1 = [3, 4, 6, 5], nums2 = [9, 1, 2, 5, 8, 3], k = 5
输出：[9, 8, 6, 5, 3]示例 2：
输入：nums1 = [6, 7], nums2 = [6, 0, 4], k = 5
输出：[6, 7, 6, 0, 4]示例 3：
输入：nums1 = [3, 9], nums2 = [8, 9], k = 3
输出：[9, 8, 9]提示
- m == nums1.length
- n == nums2.length
- 1 <= m, n <= 500
- 0 <= nums1[i], nums2[i] <= 9
- 1 <= k <= m + n
解题思路
方法：单调栈 + 归并
这道题可以分解为三个子问题：
- 从一个数组中选出指定长度的最大子序列
- 合并两个子序列得到最大数
- 枚举两个数组分别选择的数字个数
关键点：
- 使用单调栈选择最大子序列
- 设计特殊的归并规则
- 正确处理相同数字的情况
具体步骤：
- 实现从单个数组选择i个数字组成最大子序列的函数
- 实现合并两个子序列得到最大数的函数
- 枚举从nums1中选择i个数字的所有可能情况
- 对每种情况，从nums2中选择k-i个数字
- 合并两个子序列，更新最大值
时间复杂度：O(k * (m + n + k)) 空间复杂度：O(k)
图解思路
单调栈过程分析表
| 步骤 | 栈内元素 | 当前数字 | 操作 | 剩余可删除数量 |
|---|---|---|---|---|
| 初始 | [] | 3 | 入栈 | 2 |
| 1 | [3] | 4 | 入栈 | 2 |
| 2 | [3,4] | 6 | 入栈 | 2 |
| 3 | [3,4,6] | 5 | 保持 | 2 |
归并过程分析表
| 数组1位置 | 数组2位置 | 选择数字 | 结果数组 | 说明 |
|---|---|---|---|---|
| 0 | 0 | 9 | [9] | 选择较大的9 |
| 0 | 1 | 8 | [9,8] | 选择8 |
| 1 | 1 | 6 | [9,8,6] | 选择6 |
代码实现
C# 实现
public class Solution {
public int[] MaxNumber(int[] nums1, int[] nums2, int k) {
int m = nums1.Length, n = nums2.Length;
int[] maxSubsequence = new int[k];
int start = Math.Max(0, k - n), end = Math.Min(k, m);
for (int i = start; i <= end; i++) {
if (k - i > n) continue;
int[] candidate = Merge(
MaxArray(nums1, i),
MaxArray(nums2, k - i),
k
);
if (Greater(candidate, 0, maxSubsequence, 0)) {
Array.Copy(candidate, maxSubsequence, k);
}
}
return maxSubsequence;
}
private int[] MaxArray(int[] nums, int k) {
int[] stack = new int[k];
int top = -1;
int remain = nums.Length - k;
foreach (int num in nums) {
while (top >= 0 && stack[top] < num && remain > 0) {
top--;
remain--;
}
if (top < k - 1) {
stack[++top] = num;
} else {
remain--;
}
}
return stack;
}
private int[] Merge(int[] nums1, int[] nums2, int k) {
int[] result = new int[k];
int i = 0, j = 0, r = 0;
while (r < k) {
if (Greater(nums1, i, nums2, j)) {
result[r++] = nums1[i++];
} else {
result[r++] = nums2[j++];
}
}
return result;
}
private bool Greater(int[] nums1, int i, int[] nums2, int j) {
while (i < nums1.Length && j < nums2.Length && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.Length ||
(i < nums1.Length && nums1[i] > nums2[j]);
}
}Python 实现
class Solution:
def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
def max_array(nums: List[int], k: int) -> List[int]:
stack = []
drop = len(nums) - k
for num in nums:
while drop and stack and stack[-1] < num:
stack.pop()
drop -= 1
stack.append(num)
return stack[:k]
def merge(A: List[int], B: List[int]) -> List[int]:
ans = []
while A or B:
bigger = A if A > B else B
ans.append(bigger[0])
bigger.pop(0)
return ans
m, n = len(nums1), len(nums2)
max_result = [0] * k
for i in range(max(0, k - n), min(k, m) + 1):
if k - i > n:
continue
candidate = merge(max_array(nums1, i), max_array(nums2, k - i))
max_result = max(max_result, candidate)
return max_resultC++ 实现
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int m = nums1.size(), n = nums2.size();
vector<int> maxSubsequence(k);
int start = max(0, k - n), end = min(k, m);
for (int i = start; i <= end; i++) {
if (k - i > n) continue;
vector<int> candidate = merge(
maxArray(nums1, i),
maxArray(nums2, k - i),
k
);
if (greater(candidate, 0, maxSubsequence, 0)) {
maxSubsequence = candidate;
}
}
return maxSubsequence;
}
private:
vector<int> maxArray(vector<int>& nums, int k) {
vector<int> stack(k);
int top = -1;
int remain = nums.size() - k;
for (int num : nums) {
while (top >= 0 && stack[top] < num && remain > 0) {
top--;
remain--;
}
if (top < k - 1) {
stack[++top] = num;
} else {
remain--;
}
}
return stack;
}
vector<int> merge(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> result(k);
int i = 0, j = 0, r = 0;
while (r < k) {
if (greater(nums1, i, nums2, j)) {
result[r++] = nums1[i++];
} else {
result[r++] = nums2[j++];
}
}
return result;
}
bool greater(vector<int>& nums1, int i, vector<int>& nums2, int j) {
while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
i++;
j++;
}
return j == nums2.size() ||
(i < nums1.size() && nums1[i] > nums2[j]);
}
};执行结果
C# 实现
- 执行用时：288 ms
- 内存消耗：45.2 MB
Python 实现
- 执行用时：892 ms
- 内存消耗：15.8 MB
C++ 实现
- 执行用时：36 ms
- 内存消耗：24.6 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 288 ms | 45.2 MB | 实现简洁，性能适中 |
| Python | 892 ms | 15.8 MB | 代码最简洁，但性能较差 |
| C++ | 36 ms | 24.6 MB | 性能最优 |
代码亮点
- 🎯 巧妙使用单调栈选择最大子序列
- 💡 设计特殊的归并规则处理相等元素
- 🔍 通过枚举优化搜索空间
- 🎨 代码模块化，逻辑清晰
常见错误分析
- 🚫 没有正确处理数组长度限制
- 🚫 归并规则处理不当
- 🚫 相同元素的比较逻辑错误
- 🚫 没有考虑所有可能的分配方案
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 单调栈+归并 | O(k(m+n+k)) | O(k) | 效率较高 | 实现复杂 |
| 暴力枚举 | O(C(m+n,k)) | O(k) | 思路简单 | 效率极低 |
相关题目
- LeetCode 316. 去除重复字母 - 中等
- LeetCode 402. 移掉K位数字 - 中等
- LeetCode 1081. 不同字符的最小子序列 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第321题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！