LeetCode Solutions
321. Create Maximum Number
Time: $O(k(m + n)^2)$ Space: $O(m + n)$
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;
}
};