题目来源
给两个数组，求最大的k位整数，该整数由两数组按数组中元素顺序组成。
看了下tags，用贪心和DP，其实大概也知道怎么做。
先找到这两数组中最大的，判断剩下的元素个数是否足够，足够就削掉前面的，往后继续判断，不够就找前面部分最大的，继续进行判读。
这个看了答案，真的是给大神们跪了…
将k分为k1，k2两部分，然后依次找出nums1，nums2里面长度为k1，k2的最大的，然后再合并成一个。
代码写的非常简洁！厉害！
代码如下：
class Solution {
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
vector<int> res;
int n1 = nums1.size(), n2 = nums2.size();
if (n1 + n2 < k)
return res;
for (int k1=max(k-n2, 0); k1<=min(n1, k); k1++) {
res = max(res, maxNumber(maxNumber(nums1, k1), maxNumber(nums2, k-k1)));
}
return res;
}
vector<int> maxNumber(const vector<int> &nums, int k)
{
int drop = nums.size() - k;
vector<int> out;
for (int num : nums) {
while (drop && out.size() && out.back() < num) {
out.pop_back();
drop--;
}
out.push_back(num);
}
out.resize(k);
return out;
}
vector<int> maxNumber(vector<int> nums1, vector<int> nums2)
{
vector<int> out;
while (nums1.size() + nums2.size()) {
vector<int> &now = nums1 > nums2 ? nums1 : nums2;
out.push_back(now[0]);
now.erase(now.begin());
}
return out;
}
};
