321. Create Maximum Number

这道题没想到怎么做，感觉套什么算法都套不上啊。。看了大神的答案。。果然。。这算个什么题呢，智商题。顶多算个分治吧，类似归并排序的思想。

首先，选k个数。假设在nums1里面选i个数，在nums2里面选k-i个数。枚举所有的i，把最优的结果记录下来就可以。这是大体思想。

下面是具体应该怎么做。

枚举了i然后呢？我们知道了nums1里面取i个数，必须让这i个数不打乱相对顺序的情况下最大，这样两个合并起来才最大。这样需要在nums1里面抛弃m - i个数。怎么抛弃m-i个数呢？从头遍历，如果当前遍历到的nums1[i]比当前结果集里的最后一个数大，说明用nums[i]替换掉当前结果集里的最后一个数，得到的结果集是最大的。那么就把当前结果集里的最后一个数抛弃。直到抛弃够了m-i个数。

两个nums都找到了当前最大的情况，然后把他俩合并。合并的时候就比较两个nums的第一个，谁大就把谁加到最终结果集里，直到两个nums都加完。

注意：

1. 在maxVector函数里，返回的必须是k长度的，那么如果nums是递减的，且长度大于k，那么按照上述做法得到的res肯定大于k，而且肯定一个都不会drop掉，所以必须在返回之前resize一下。

2. 在主函数里那个for循环看了好久才看明白。这个for循环的意思是这样的：我希望i表示的是从nums1里面取i个数。那么如果k特别小，小于nums1的长度，那么i可以从0开始，取到k，换句话说，我可以从nums1里面取0个，取1个，取2个。。。取k个，所以终止条件是i <= min(k, m)。那么如果k比较大，大于nums2了，那么nums2取整个数组也不够k。所以nums1至少取k-n个。所以开始条件里面的i = max(0, k - n)就是用来处理这种nums1里面最少取多少个的情况，这样小于这个数的就不用考虑了，因为一定不能取满k个数。

class Solution {
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        vector<int> res;
        for (int i = max(0, k - n); i <= min(k, m); ++i) {
            res = max(res, mergeVector(maxVector(nums1, i), maxVector(nums2, k - i)));
        }
        return res;
    }
    vector<int> maxVector(vector<int> nums, int k) {
        int drop = nums.size() - k;
        vector<int> res;
        for (int num : nums) {
            while (drop && res.size() && res.back() < num) {
                res.pop_back();
                --drop;
            }
            res.push_back(num);
        }
        res.resize(k);
        return res;
    }
    vector<int> mergeVector(vector<int> nums1, vector<int> nums2) {
        vector<int> res;
        while (nums1.size() + nums2.size()) {
            vector<int> &tmp = nums1 > nums2 ? nums1 : nums2;
            res.push_back(tmp[0]);
            tmp.erase(tmp.begin());
        }
        return res;
    }
};