321. Create Maximum Number

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.

Note: You should try to optimize your time and space complexity.

Example 1:

Input:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
Output:
[9, 8, 6, 5, 3]

Example 2:

Input:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
Output:
[6, 7, 6, 0, 4]

Example 3:

Input:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
Output:
[9, 8, 9]

bool greater(const vector<int>& nums1, int i, const 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> mergeVector(const vector<int>& nums1, const vector<int>& nums2) {
    int i = 0, j = 0, m = nums1.size(), n = nums2.size();
    vector<int> res;
    res.reserve(m + n);
    while (i < m || j < n) {
        res.push_back(greater(nums1, i, nums2, j) ? nums1[i++] : nums2[j++]);
    }
    return res;
}
vector<int> maxVector(const vector<int>& nums, int k) {
    int need_to_del = nums.size() - k;
    vector<int> res;
    res.reserve(k);
    for (int num : nums) {
        while (need_to_del > 0 && !res.empty() && res.back() < num) {
            res.pop_back();
            --need_to_del;
        }
        res.push_back(num);
    }
    res.resize(k);
    return res;
}
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
    int m = nums1.size(), n = nums2.size();
    vector<int> res;
    // 0 <= i <= m -> i >= 0 && i <= m
    // 0 <= k - i <= n -> i >= k - n && i <= k
    for (int i = max(0, k - n); i <= min(k, m); ++i) {
        // res = max(res, mergeVector(maxVector(nums1, i), maxVector(nums2, k - i) ) );
        vector<int> vec1 = maxVector(nums1, i), vec2 = maxVector(nums2, k - i);
        vector<int> merge = mergeVector(vec1, vec2);
        if (greater(merge, 0, res, 0)) res = merge;
    }
    return res;
}