已知长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，直观地表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
求满足该条件的最大数。结果返回一个表示该最大数的长度为k的数组。
尽可能优化你的算法的时间和空间复杂度。
例 1:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
返回 [9, 8, 6, 5, 3]
例 2:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
返回 [6, 7, 6, 0, 4]
例 3:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
返回 [9, 8, 9]
详见：https://leetcode.com/problems/create-maximum-number/description/
C++：
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k)
{
int m = nums1.size();
int n = nums2.size();
vector<int> result(k);
for (int i = std::max(0 , k - n); i <= k && i <= m; ++i)
{
auto v1 = maxArray(nums1, i);
auto v2 = maxArray(nums2, k - i);
vector<int> candidate = merge(v1, v2, k);
if (greater(candidate, 0, result, 0))
{
result = candidate;
}
}
return result;
}
bool greater(vector<int>& nums1, int i, vector<int>& nums2, int j)
{
while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j])
{
i++;
j++;
}
return j == nums2.size() || (i<nums1.size() && nums1[i] > nums2[j]);
}
vector<int> merge(vector<int>& nums1, vector<int>& nums2, int k)
{
std::vector<int> ans(k);
int i = 0, j = 0;
for (int r = 0; r<k; r++){
if( greater(nums1, i, nums2, j) )
{
ans[r] = nums1[i++] ;
}
else
{
ans[r] = nums2[j++];
}
}
return ans;
}
vector<int> maxArray(vector<int>& nums, int k)
{
int n = nums.size();
vector<int> result(k);
for (int i = 0, j = 0; i < n; i++)
{
while (n - i + j>k && j > 0 && result[j-1] < nums[i])
{
j--;
}
if (j < k)
{
result[j++] = nums[i];
}
}
return result;
}
};
参考：https://www.cnblogs.com/CarryPotMan/p/5384172.html