题目描述

给定两个数组，长度分别是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]

算法

(贪心) $O(n^3)$

原问题直接处理比较困难，我们分成三步来做：

1. 先枚举从两个数组中分别选多少个数；
2. 然后分别贪心求解每个数组中需要选那些数；
3. 将选出的两个数列合并；

第1步直接循环枚举即可。

第2步，由于我们要使最终选出的数列的字典序最大，所以我们从每个数组中选出的数列的字典序也要尽可能大。
这一步可以用贪心来做，从前往后选，如果当前数比选出的数列的末尾数字大，则删掉末尾数字，直到当前数小于等于末尾数字，或再删就不能选出足够数字为止，然后将当前数插入数列末尾。

第3步，也用贪心来做，每次要选择将哪个数列的开头插入结果数列。我们比较两个数列的字典序，优先从字典序大的数列中选。

时间复杂度分析：第一步有 $n$ 种选择，第二步和第三步是并列的，第二步的计算量是 $O(n)$ 级别的，第三步的计算量是 $O(n^2)$ 级别的，所以总时间复杂度是 $O(n^3)$。

C++ 代码

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size(), m = nums2.size();
        vector<int> res(k, INT_MIN);
        for (int i = max(0, k - m); i <= k && i <= n; i ++ )
        {
            vector<int> N = maxArray(nums1, i);
            vector<int> M = maxArray(nums2, k - i);
            vector<int> temp = merge(N, M);
            if (res < temp) res = temp;
        }
        return res;
    }

    vector<int> merge(vector<int>& N, vector<int>& M)
    {
        vector<int> res;
        while (N.size() && M.size())
            if (N > M)
                res.push_back(N[0]), N.erase(N.begin());
            else
                res.push_back(M[0]), M.erase(M.begin());
        while (N.size()) res.push_back(N[0]), N.erase(N.begin());
        while (M.size()) res.push_back(M[0]), M.erase(M.begin());
        return res;
    }

    vector<int> maxArray(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<int> res(k);
        for (int i = 0, j = 0; i < n; i ++ )
        {
            while (n - i + j > k && j && res[j - 1] < nums[i]) j -- ;
            if (j < k) res[j ++ ] = nums[i];
        }
        return res;
    }
};