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)``。