LeetCode 321. 拼接最大数***

涉及以下点：

1. 如何利用单调栈寻找不连续保持相对位置的前k个值；
2. 字符串合并问题；

class Solution {
public:
    vector maxNumber(vector& nums1, vector& nums2, int k) {
        int m=nums1.size();
        int n=nums2.size();
        int start=max(0,k-n),end=min(k,m);//即总和为k情况，start能有多少个位置；
        vector cur(k,0);
        for(int i=start;i<=end;i++){
            vector q1=pick(nums1, i);
            vector q2=pick(nums2,k-i);
            vector ret=merage_(q1, q2);
            if(cmp(ret, cur,0,0))
                cur=ret;
        }
        return cur;
    }

    vector pick(vector& vec,int k){
        vector st;
        int index=0;
        int remain=vec.size()-k;//需要剔除多少个元素；
        for(int i=0;i
            while(!st.empty()&&vec[i]>*st.rbegin()&&remain>0){
                remain--;
                st.pop_back();
                index--;
            }
            if(index
                st.push_back(vec[i]);
                index++;
            }else{
                remain--;
            }
        }
        return st;
    }

    vector merage_(vector& a,vector& b){
        vectorret;
        for(int i1=0,i2=0;i1!=a.size()||i2!=b.size();){
            if(i1==a.size()){
                ret.push_back(b[i2++]);
                continue;
            }
            if(i2==b.size()){
                ret.push_back(a[i1++]);
                continue;
            }
            if(a[i1]>b[i2]){
                ret.push_back(a[i1++]);
            }else if(a[i1]
                ret.push_back(b[i2++]);
            }else{
                int que=cmp(a,b,i1,i2);
                if(cmp(a, b, i1, i2)>0){
                    ret.push_back(a[i1++]);
                }else{
                    ret.push_back(b[i2++]);
                }
            }
        }
        return ret;
    }

    bool cmp(vector& a,vector& b,int i1,int i2){
        int m=a.size();
        int n=b.size();
        while(i1
            if(a[i1]==b[i2]){
                i1++,i2++;
                continue;
            }
            if(a[i1]>b[i2])
                return true;
            else
                return false;
        }
        return (m-i1)>(n-i2);
    }
};```