## Create Maximum Number

• Time:O(k(m + n)^2)
• Space:O(m + n)

## C++

``````class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> ans;

for (int k1 = 0; k1 <= k; ++k1) {
const int k2 = k - k1;
if (k1 > nums1.size() || k2 > nums2.size())
continue;
ans = max(ans, maxNumber(maxNumber(nums1, k1), maxNumber(nums2, k2)));
}

return ans;
}

private:
vector<int> maxNumber(const vector<int>& nums, int k) {
if (k == 0)
return {};

vector<int> ans;
int toPop = nums.size() - k;

for (const int num : nums) {
while (!ans.empty() && ans.back() < num && toPop-- > 0)
ans.pop_back();
ans.push_back(num);
}

return {begin(ans), begin(ans) + k};
}

private:
vector<int> maxNumber(const vector<int>& nums1, const vector<int>& nums2) {
vector<int> ans;

auto s1 = cbegin(nums1);
auto s2 = cbegin(nums2);

while (s1 != cend(nums1) || s2 != cend(nums2))
if (lexicographical_compare(s1, cend(nums1), s2, cend(nums2)))
ans.push_back(*s2++);
else
ans.push_back(*s1++);

return ans;
}
};
``````