天池 在线编程 删除字符（单调栈）

例1:
输入:str="fskacsbi",k=2
输出:"ab"
解释:“ab“是str中长度为2并且字典序最小的子串

例2:
输入:str="fsakbacsi",k=3
输出:"aac"

class Solution {
public:
    /**
     * @param str: the string
     * @param k: the length
     * @return: the substring with  the smallest lexicographic order
     */
    string deleteChar(string &str, int k) {
        // Write your code here.
        int n = str.size();
        if(k >= n)//不用删
            return str;
        int del = n-k;//要删除的个数
        stack<char> stk;
        for(int i = 0; i < n; i++)
        {
            while(!stk.empty() && stk.top() > str[i] && del)
            {	//还可删del > 0 且 前面的字符比当前的大，删除之
                stk.pop();
                del--;
            }
            stk.push(str[i]);
        }
        while(del--)//还没删完的，从尾巴开始删
            stk.pop();
        string ans;
        while(!stk.empty())
        {
            ans = stk.top() + ans;
            stk.pop();
        }
        return ans;
    }
};