321. Create Maximum Number

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

先得解决一个简单一点的问题————从一个数组里挑出k个数字组成最大的数。

注意1：
merge的时候如果相同，要比较下一个数字，比如 [6,0]和[6,7]要选择后者。
如果是[6,0]和[6]呢？选哪个都可以
如果是[6,7]和[6]呢？选[6,7]
如果是[6,7,8]和[6,7,1]呢？选[6,7,8]
所以，后一位行不通，后面要一直比较到完才行。

注意2：
注意求一个数组里的k个数字组成的最大数的时候，要判断st.size()+n-i>k

class Solution {
    vector<int> maxVec(vector<int>& nums, int k) {
        if(k == 0) return {};
        int n = nums.size();
        stack<int> st;
        for(int i = 0; i < n; i++) {
            while(!st.empty() && st.size() + n - i > k && st.top() < nums[i])
                st.pop();
            if(st.size() < k) 
                st.push(nums[i]);
        }
        
        vector<int> res(k);
        while(!st.empty()){
            res[--k] = st.top(); 
            st.pop();
        }
        return res;
    }
    
    vector<int> merge(vector<int>& v1, vector<int>& v2, int k) {
        vector<int> m(k);
        int i = 0, j = 0;
        int mi = 0;
        while(i < v1.size() && j < v2.size()) {
            if(isGreater(v1,i,v2,j))
                m[mi++] = v1[i++];
            else 
                m[mi++] = v2[j++];
        }
        for(;i<v1.size();i++)
            m[mi++] = v1[i];
        for(;j<v2.size();j++)
            m[mi++] = v2[j];
        return m;
    }
    
    //return true if nums1,i is greater than nums2,j 
    bool isGreater(vector<int> &nums1, int i, vector<int> &nums2, int j) {
        while (i < nums1.size() && j < nums2.size() && nums1[i] == nums2[j]) {
            ++i;
            ++j;
        }
        if (j == nums2.size()) return true;
        if (i < nums1.size() && nums1[i] > nums2[j]) return true;
        return false;
    }
    
    void print(vector<int> & v){
        for(int i = 0; i < v.size(); i++)
            cout<<v[i]<<" ";
        cout<<endl;
    }
    
public:
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m = nums1.size();
        int n = nums2.size();
        vector<int> res;
        for(int i = 0; i <= k; i++) {
            if(i > nums1.size() || k - i > nums2.size()) 
                continue;
            vector<int> v1 = maxVec(nums1,i);
            //cout<<"v1= ";print(v1);
            vector<int> v2 = maxVec(nums2,k-i);
            //cout<<"v2= ";print(v2);
            vector<int> tmpres = merge(v1,v2,k);
            //cout<<"tmpres= ";print(tmpres);
            if(isGreater(tmpres,0,res,0))
                res = tmpres;
        }
        return res;
    }
};