2017-01-06

Leetcode 321. Create Maximum Number【贪心】

题目链接：

https://leetcode.com/problems/create-maximum-number/

题意：

给定两个数组，从其中选出$k$个数，要求保持原数组中数的顺序不变，使得他们组成的数最大。

分析：

写起来比较麻烦的一道题。
首先枚举在两个数组中分别选择的元素个数。
然后分别选出能组成的最大数的元素。
接下来将得到的元素进行合并，直接两个指针一个一个比较，贪心的选择大的那个。对于指向相同元素的情况，往后继续走，直到某个数组走到尽头或者两个指针指向的元素不同即可。
如何选出某个数组所能组成最大数？

可以参考Remove Duplicate Letters，采用栈的解决方法。
$dp$，定义$dp[i][j]$为从该数组中选择$i$个元素，其中最后一个元素是第$j$个元素时组成的最大数。可以将数组都转化为字符串，方便比较大小。

两个方法最坏情况时间复杂度都是$O(n^3)$.

代码：

$Dicuss$中有更优美的写法，= = 我这个有点丑

class Solution {
public:
    vector<int>choose(vector<int>& nums, int k){
        int sz = nums.size();
        vector<int> ans;
        if(k == 0) return ans;
        if(k > nums.size()) return nums;
        ans = vector<int>(k, 0);
        int top = 0;
        for(int i = 0; i < sz; ++i){
            while(top && sz - i + top > k && nums[i] > ans[top - 1]) top--;
            if(top < k) ans[top++] = nums[i];
        }
        return ans;
    }
    vector<int> getk(vector<int>& nums1, vector<int>& nums2, int k){
        int l = 0, r = 0;
        vector<int> ans;
        int sz1 = nums1.size();
        int sz2 = nums2.size();
        while((l < sz1 || r < sz2) && ans.size() < k){
            int tl = l, tr = r;
            while(tl < sz1 && tr < sz2 && nums1[tl] == nums2[tr]){
                tl++;tr++;
            }
            if(tl == sz1) ans.push_back(nums2[r++]);
            else if(tr == sz2) ans.push_back(nums1[l++]);
            else if(nums1[tl] < nums2[tr]) ans.push_back(nums2[r++]);
            else ans.push_back(nums1[l++]);
        }
        return ans;
    }
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<int>res(k, 0);
        vector<int>ans(k, 0);
        int sz1 = nums1.size();
        int sz2 = nums2.size();
        for(int i = max(0, k - sz2); i <= min(k, sz1); ++i){
            vector<int>v1 = choose(nums1, i);
            vector<int>v2 = choose(nums2, k - i);
            res = getk(v1, v2, k);
            if(res.size() != k) continue;
            int sz = res.size();
            for(int j = 0; j < sz; ++j){
                if(res[j] < ans[j]) break;
                if(res[j] > ans[j]){
                    ans = res;
                    break;
                }
            }
        }
        return ans;
    }
};