单调栈的高级用法

[x] 402. 移掉 K 位数字(中等)，低频
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意: num 的长度小于 10002 且 ≥ k。 num 不会包含任何前导零。

示例 1 : 输入: num = “1432219”, k = 3 输出: “1219” 解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 : 输入: num = “10200”, k = 1 输出: “200” 解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

    string removeKdigits(string num, int k) {
        if(num.empty()==true||k<=0){
            return num;
        }
        //默写单调栈
        stack<char> stk;
        for(auto c:num){
            while(k>0&&stk.empty()==false&&stk.top()>c){
                stk.pop();
                --k;
            }
            //不允许在栈为空的时候放入0(防止前缀0)
            if(c=='0'&&stk.empty()==true){
                continue;
            }
            stk.push(c);
        }
        while(k>0&&stk.empty()==false){
            stk.pop();
            k--;
        }
        //整理返回值
        string ret;
        while(stk.empty()==false){
            ret+=stk.top();
            stk.pop();
        }
        //cout << ret;
        if(ret==""){
            ret="0";
        }else{
            reverse(ret.begin(),ret.end());
        }
        return ret;
    }

• 321. 拼接最大数(困难)，低频

注意的坑：
这里用单调栈得到的移除K个元素之后得到的只是最大而已，并不能保证结果的单调性。所以这里容易用合并两个有序数组的策略来进行merge。
这段代码用来归并两个有序数组是没问题的：

    vector<int> mergeMotonic(vector<int>& nums1, vector<int>& nums2){
        int m=nums1.size();
        int n=nums2.size();
        vector<int> ret(m+n);
        int i=0;
        int j=0;
        int k=0;
        while(i<m&&j<n){
            if(nums1[i]>nums2[j]){
                ret[k++]=nums1[i++];
            }else{
                ret[k++]=nums2[j++];
            }
        }
        while(i<m){
            ret[k++]=nums1[i++];
        }
        while(j<n){
            ret[k++]=nums2[j++];
        }
        return ret;
    }

但是非有序数组的合并一点也不容易想得到：

    vector<int> mergeMotonic(vector<int>& nums1, vector<int>& nums2){
        int m=nums1.size();
        int n=nums2.size();
        vector<int> ret(m+n);
        int i=0;
        int j=0;
        int k=0;
        while(k<m+n){
            if(compare(nums1,i,nums2,j)>0){
                ret[k++]=nums1[i++];
            }else{
                ret[k++]=nums2[j++];
            }
        }
        return ret;
    }
    int compare(vector<int>& nums1, int i, vector<int>& nums2, int j){
        int m=nums1.size();
        int n=nums2.size();
        while(i<m&&j<n){
            int equal=nums1[i++]-nums2[j++];
            if(equal!=0) return equal;
        }
        return (m-i)-(n-j);
    }

容易进入的坑二：
比较两个数组的大小，容易写成深搜的样子：

    bool isUpper(vector<int>& nums1, vector<int>& nums2, int n){
        //if nums2 > nums1 return true; or false;
        for(int i=0;i<n;++i){
            if(nums1[i]>nums2[i]){
                return false;
            }
        }
        return true;
    }

这是错误的，用例nums1为[9,8,7,6]，nums2为[9,9,6,5]。返回的是false，就不是正确的答案。正确的应该是这样的：

    bool isUpper(vector<int>& nums1, vector<int>& nums2, int n){
        //if nums2 > nums1 return true; or false;
        for(int i=0;i<n;++i){
            //一次比较就可以得知大小
            if(nums1[i]>nums2[i]){
                return false;
            }else if(nums2[i]>nums1[i]){
                return true;
            }
        }
        return false;//两者如果相等，容易遗漏
    }

解题思路为拆分K到nums1、nums2，枚举出次拆分下的最优，再merge成K长度的策略，很像后序遍历，迭代下的后序遍历：

    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) {
        int m=nums1.size();
        int n=nums2.size();
        int start=max(k-n,0);
        int end=min(m,k);
        vector<int> ret(k,0);
        //拆分枚举策略
        for(int i=start;i<=end;++i){
            vector<int> vec1=getMotonic(nums1,i);
            vector<int> vec2=getMotonic(nums2,k-i);
            vector<int> cur=mergeMotonic(vec1,vec2);
            if(isUpper(ret,cur,k)){
                swap(ret,cur);
            }
        }
        return ret;
    }

单调栈求解保留K个元素时的最大值：

    vector<int> getMotonic(vector<int>& nums,int k){
        stack<int> stk;
        int drop=nums.size()-k;
        for(auto c:nums){
            while(!stk.empty()&&stk.top()<c&&drop>0){
                stk.pop();
                --drop;
            }
            if(stk.size()<k){
                stk.push(c);
            }else{
                drop--;
            }
        }
        vector<int> ret;
        while(!stk.empty()){
            ret.emplace_back(stk.top());
            stk.pop();
        }
        reverse(ret.begin(),ret.end());
        return ret;
    }

填坑之后的merge和比较函数：

    vector<int> mergeMotonic(vector<int>& nums1, vector<int>& nums2){
        int m=nums1.size();
        int n=nums2.size();
        vector<int> ret(m+n);
        int i=0;
        int j=0;
        int k=0;
        while(k<m+n){
            if(compare(nums1,i,nums2,j)>0){
                ret[k++]=nums1[i++];
            }else{
                ret[k++]=nums2[j++];
            }
        }
        return std::move(ret);
    }
    int compare(vector<int>& nums1, int i, vector<int>& nums2, int j){
        int m=nums1.size();
        int n=nums2.size();
        while(i<m&&j<n){
            int equal=nums1[i++]-nums2[j++];
            if(equal!=0) return equal;
        }
        return (m-i)-(n-j);
    }
    bool isUpper(vector<int>& nums1, vector<int>& nums2, int n){
        //if nums2 > nums1 return true; or false;
        for(int i=0;i<n;++i){
            if(nums1[i]>nums2[i]){
                return false;
            }else if(nums2[i]>nums1[i]){
                return true;
            }
        }
        return false;
    }

如果面试巧遇这道题，怕会是滑铁卢啊。