321 Create Maximum Number 拼接最大数

已知长度分别为 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]

详见：https://leetcode.com/problems/create-maximum-number/description/

C++：

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
    {
        int m = nums1.size();
        int n = nums2.size();
        vector<int> result(k);
        for (int i = std::max(0 , k - n); i <= k && i <= m; ++i)
        {
            auto v1 = maxArray(nums1, i);
            auto v2 = maxArray(nums2, k - i);
            vector<int> candidate = merge(v1, v2, k);
            if (greater(candidate, 0, result, 0))
            {
                result = candidate;
            }
        }
        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]);
    }

    vector<int> merge(vector<int>& nums1, vector<int>& nums2, int k) 
    {
        std::vector<int> ans(k);
        int i = 0, j = 0;
        for (int r = 0; r<k; r++){
            if( greater(nums1, i, nums2, j) ) 
            {
                ans[r] = nums1[i++] ;
            }
            else
            {
                ans[r] = nums2[j++];
            }
        }
        return ans;
    }
    vector<int> maxArray(vector<int>& nums, int k)
    {
        int n = nums.size();
        vector<int> result(k);
        for (int i = 0, j = 0; i < n; i++)
        {
            while (n - i + j>k && j > 0 && result[j-1] < nums[i])
            {
                j--;
            }
            if (j < k) 
            {
                result[j++] = nums[i];
            }
        }
        return result;
    }
};

 参考：https://www.cnblogs.com/CarryPotMan/p/5384172.html