LeetCode 321. 拼接最大数***

具体思路：

涉及以下点：

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

具体代码：

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

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

    vector<int> merage_(vector<int>& a,vector<int>& b){
    
        vector<int>ret;
        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]<b[i2]){
    
                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<int>& a,vector<int>& b,int i1,int i2){
    
        int m=a.size();
        int n=b.size();
        while(i1<m&&i2<n){
       if(a[i1]==b[i2]){
       i1++,i2++; continue; } if(a[i1]>b[i2]) return true; else return false; } return (m-i1)>(n-i2);
    }
};```