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; } };