0321. Create Maximum Number¶
题目信息¶
- 题号:
0321
- 难度:
Hard
- 主题:
数字数组、子序列合并、相对顺序、字典序最大
- 原题:
- 重点:
必须恰好选择 k 个数字、两个数组内部顺序分别保持、返回字典序最大的数字序列
题目重述¶
给定两个数字数组 nums1 和 nums2,它们分别表示两个不含前导零的十进制数,以及整数 k。从两个数组中合计选择恰好 k 个数字,并按选择后的顺序组成长度为 k 的结果数组。
来自同一个原数组的数字必须保持原有相对顺序,来自不同数组的数字可以交错排列。返回所有合法选择中字典序最大的结果。两个数组长度均位于 [1, 500],元素位于 [0, 9],并满足 1 <= k <= nums1.length + nums2.length。
自建示例¶
需要舍弃一个较早的小数字:
输入:nums1 = [6, 7],nums2 = [6, 0, 4],k = 4
输出:[7, 6, 0, 4]
解释:从 nums1 只选择 7,从 nums2 选择全部数字并合并,可让首位成为 7;任何以 6 开头的合法结果都更小。
选择全部数字时仍要保持各自顺序:
输入:nums1 = [8, 1],nums2 = [7, 9],k = 4
输出:[8, 7, 9, 1]
解释:四个数字都必须使用;nums1 中 8 必须在 1 前,nums2 中 7 必须在 9 前,在这些限制下该合并结果字典序最大。
拆成“各取多少”与“如何交错”¶
最优答案一定有一个确定的分配:从 nums1 取 take1 个,从 nums2 取 k - take1 个。枚举这个分配后,问题分成两步。第一步,在每个数组内部取指定数量的字典序最大子序列;第二步,把两个子序列交错合并成最大的整体序列。枚举范围限制为两边都能取够数字的范围。
固定取 t 个数字时,使用单调栈从左到右构造最大子序列。允许丢弃 length - t 个数字;当前数字比栈顶大且仍有丢弃额度时,弹出栈顶可以让更大的数字提前出现。扫描结束若额度尚未用完,就从尾部删除。这个贪心保留了原数组内部顺序。
合并时不能只比较两个当前数字:如果两边当前数字相等,后续较大的位置决定哪一边应先取。每次比较两个剩余后缀的字典序,选择较大的后缀的首位;相等后缀任选一边都得到同一个结果。对所有分配取最大候选即可覆盖全部合法答案。
C++ 实现¶
class Solution {
std::vector<int> maxSubsequence(
const std::vector<int>& nums, int length) {
std::vector<int> stack;
int drop = static_cast<int>(nums.size()) - length;
for (int value : nums) {
while (drop > 0 && !stack.empty()
&& stack.back() < value) {
stack.pop_back();
--drop;
}
stack.push_back(value);
}
stack.resize(length);
return stack;
}
bool greaterSuffix(const std::vector<int>& first, int i,
const std::vector<int>& second, int j) {
while (i < static_cast<int>(first.size())
&& j < static_cast<int>(second.size())
&& first[i] == second[j]) {
++i;
++j;
}
return j == static_cast<int>(second.size())
|| (i < static_cast<int>(first.size())
&& first[i] > second[j]);
}
std::vector<int> merge(const std::vector<int>& first,
const std::vector<int>& second) {
std::vector<int> result;
int i = 0;
int j = 0;
while (i < static_cast<int>(first.size())
|| j < static_cast<int>(second.size())) {
if (greaterSuffix(first, i, second, j)) {
result.push_back(first[i++]);
} else {
result.push_back(second[j++]);
}
}
return result;
}
public:
std::vector<int> maxNumber(std::vector<int>& nums1,
std::vector<int>& nums2, int k) {
int n1 = static_cast<int>(nums1.size());
int n2 = static_cast<int>(nums2.size());
int low = std::max(0, k - n2);
int high = std::min(k, n1);
std::vector<int> answer;
for (int take1 = low; take1 <= high; ++take1) {
int take2 = k - take1;
std::vector<int> first = maxSubsequence(nums1, take1);
std::vector<int> second = maxSubsequence(nums2, take2);
std::vector<int> candidate = merge(first, second);
if (candidate > answer) answer = candidate;
}
return answer;
}
};
代码分析¶
maxSubsequence 只删除不会影响长度下限的较小前缀,保证固定取数数量下的最优性;greaterSuffix 在当前数字相等时继续比较后缀,避免把“当前相等”错误地当成任意选择。每一种合法的取数分配都会被枚举,因此全局最优不会遗漏。设候选分配数为 s,单调栈部分为 O(s(n1+n2));简单后缀比较在大量相等数字时可能重复扫描,合并最坏为 O(k^2),总复杂度可写为 O(s(n1+n2+k^2)),额外空间为 O(k)。