0321. Create Maximum Number
===========================
题目信息
--------
:题号: 0321
:难度: Hard
:主题: 数字数组、子序列合并、相对顺序、字典序最大
:原题: `LeetCode 0321 `_
:重点: 必须恰好选择 k 个数字、两个数组内部顺序分别保持、返回字典序最大的数字序列
题目重述
--------
给定两个数字数组 ``nums1`` 和 ``nums2``,它们分别表示两个不含前导零的十进制数,以及整数 ``k``。从两个数组中合计选择恰好 ``k`` 个数字,并按选择后的顺序组成长度为 ``k`` 的结果数组。
来自同一个原数组的数字必须保持原有相对顺序,来自不同数组的数字可以交错排列。返回所有合法选择中字典序最大的结果。两个数组长度均位于 ``[1, 500]``,元素位于 ``[0, 9]``,并满足 ``1 <= k <= nums1.length + nums2.length``。
自建示例
--------
需要舍弃一个较早的小数字:
.. code-block:: text
输入:nums1 = [6, 7],nums2 = [6, 0, 4],k = 4
输出:[7, 6, 0, 4]
解释:从 nums1 只选择 7,从 nums2 选择全部数字并合并,可让首位成为 7;任何以 6 开头的合法结果都更小。
选择全部数字时仍要保持各自顺序:
.. code-block:: text
输入: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++ 实现
--------
.. code-block:: cpp
class Solution {
std::vector maxSubsequence(
const std::vector& nums, int length) {
std::vector stack;
int drop = static_cast(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& first, int i,
const std::vector& second, int j) {
while (i < static_cast(first.size())
&& j < static_cast(second.size())
&& first[i] == second[j]) {
++i;
++j;
}
return j == static_cast(second.size())
|| (i < static_cast(first.size())
&& first[i] > second[j]);
}
std::vector merge(const std::vector& first,
const std::vector& second) {
std::vector result;
int i = 0;
int j = 0;
while (i < static_cast(first.size())
|| j < static_cast(second.size())) {
if (greaterSuffix(first, i, second, j)) {
result.push_back(first[i++]);
} else {
result.push_back(second[j++]);
}
}
return result;
}
public:
std::vector maxNumber(std::vector& nums1,
std::vector& nums2, int k) {
int n1 = static_cast(nums1.size());
int n2 = static_cast(nums2.size());
int low = std::max(0, k - n2);
int high = std::min(k, n1);
std::vector answer;
for (int take1 = low; take1 <= high; ++take1) {
int take2 = k - take1;
std::vector first = maxSubsequence(nums1, take1);
std::vector second = maxSubsequence(nums2, take2);
std::vector 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)``。