Create Maximum Number

Desicription

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:

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

Example 2:

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

Example 3:

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    std::vector<int> maxNumber(const std::vector<int>& nums1, const std::vector<int>& nums2, int k) const {
        auto res = std::vector<int>();
        for(int k1 = std::max(0, k - (int)nums2.size()); k1 <= std::min(k, (int)nums1.size()); k1++) {
            res = std::max(res, maxNumber(maxNumber(nums1, k1), maxNumber(nums2, k - k1)));
        }

        return res;
    }

    std::vector<int> maxNumber(const std::vector<int>& nums, int k) const {
        int dropCount = nums.size() - k;
        auto stack = std::stack<int>();
        for(auto num : nums) {
            while(dropCount != 0 && !stack.empty() && stack.top() < num) {
                stack.pop();
                dropCount--;
            }
            stack.push(num);
        }

        auto res = std::vector<int>(k);
        while(stack.size() > k) {
            stack.pop();
        }
        for(int i = res.size() - 1; i >= 0; i--) {
            res[i] = stack.top();
            stack.pop();
        }
        return res;
    }

    std::vector<int> maxNumber(const std::vector<int>& nums1, const std::vector<int>& nums2) const {
        auto res = std::vector<int>(nums1.size() + nums2.size());
        auto it1 = nums1.begin();
        auto it2 = nums2.begin();
        for(auto& num : res) {
            num = std::lexicographical_compare(it1, nums1.end(), it2, nums2.end()) ? *it2++ : *it1++;
        }
        return res;
    }
};