leetcode 321 - Create Maximum Number

https://leetcode.com/problems/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]

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int size1 = nums1.size();
int size2 = nums2.size();

vector<int> max_num;

for (int len1 = 0; len1 <= min(size1, k); len1++) {
int len2 = k - len1;

if (len2 < 0 || len2 > size2) continue;

vector<int> n1 = get_k_max_num(nums1, len1);
vector<int> n2 = get_k_max_num(nums2, len2);
vector<int> n = merge(n1, n2);
if (greater(n, 0, max_num, 0))
max_num = n;
}

return max_num;
}

vector<int> get_k_max_num(vector<int> &num, int k) {
vector<int> stk;
int size = num.size();

for (int i = 0; i < size; i++) {
int remain = size - i - 1;

while (!stk.empty() && num[i] > stk.back() &&
(int)stk.size() + remain >= k) {
stk.pop_back();
}

stk.push_back(num[i]);
}

if (stk.size() > k)
stk.resize(k);

return stk;
}

vector<int> merge(vector<int> &nums1, vector<int> &nums2) {
int size1 = nums1.size();
int size2 = nums2.size();

vector<int> result;

int i = 0, j = 0;
while (i < size1 || j < size2) {
if (greater(nums1, i, nums2, j))
result.push_back(nums1[i++]);
else
result.push_back(nums2[j++]);
}

return result;
}

bool greater(vector<int> &nums1, int i, vector<int> &nums2, int j) {
int size1 = nums1.size();
int size2 = nums2.size();

while (i < size1 || j < size2) {
if (i == size1) return false;
if (j == size2) return true;

if (nums1[i] > nums2[j]) return true;
if (nums1[i] < nums2[j]) return false;

i++;
j++;
}

return false;
}
};