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]
Approach #1: C++. [greedy + dp]
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
int n1 = nums1.size();
int n2 = nums2.size();
vector<int> ans;
for (int k1 = 0; k1 <= k; ++k1) {
int k2 = k - k1;
if (k1 > n1 || k2 > n2) continue;
ans = max(ans, maxNum(maxNum(nums1, k1), maxNum(nums2, k2)));
}
return ans;
}
private:
vector<int> maxNum(const vector<int>& nums, int k) {
if (k == 0) return {};
vector<int> ans;
int to_pop = nums.size() - k;
for (auto num : nums) {
while (!ans.empty() && num > ans.back() && to_pop-- > 0)
ans.pop_back();
ans.push_back(num);
}
ans.resize(k);
return ans;
}
vector<int> maxNum(const vector<int>& nums1, const vector<int>& nums2) {
vector<int> ans;
auto s1 = nums1.cbegin();
auto e1 = nums1.cend();
auto s2 = nums2.cbegin();
auto e2 = nums2.cend();
int index = 0;
while (s1 != e1 || s2 != e2)
ans.push_back(lexicographical_compare(s1, e1, s2, e2) ? *s2++ : *s1++);
return ans;
}
};
reference:
321. Create Maximum Number (c++ ——> lexicographical_compare)
原文：https://www.cnblogs.com/ruruozhenhao/p/10203336.html