leetcode 402.移掉k位数字

暴力的话我只能优化到这里了，也就是只能过31个样例，思路就是对于每一位字符，如果当前的字符小于下一个字符，那么就加进去结果，否则就是需要删除的字符，然后次数++。

class Solution {
public:
    string removeKdigits(string num, int k) {
        if(num=="0")
        return "0";
        if(num.size()==k)
        return "0";
        string s;
        string buf=num;
        sort(buf.begin(),buf.end());
        if(buf==num)
        {buf.resize(num.size()-k);
        return buf;
        }
        else{
        int count=0;
        int index=0;
        for(int i=0;i<num.size()-1;i++){
            if(num[i]<num[i+1])
            s+=num[i];
            else
            {
                count++;
            }
            if(count==k)
            {
                index=i+1;
                break;
            }
        }
        s+=num.substr(index);
        int index2=0;
        while(s[index2]=='0'&&s.size()>1){
            index2++;
        }
        if(index2==s.size())
        return "0";
        else
        return s.substr(index2);
    }
    }
};

其实上面的思路已经很接近正确的贪心思路了。其实这个思路暴力下去是对的，但是对于前导0的判断并不是很会，所以在判断前导0的时候会把不是前导0的0也去掉了，所以这个做法是有待优化的做法，并不是思路不对。

接下来就是对于正解的解读了：贪心+单调栈。

我们发现，可以用一个栈进行存储数字，然后在栈顶判断下一个元素是否可以加进来，如果比当前的元素大，那么就入栈，否则就出栈，也就是我们说的删除元素；这个循环停止有三个条件：

1.这个栈空的时候；

2.当我们的删除次数用完的时候；

3.当前的元素对比下一个元素并不是大于关系。

并列条件，所以有一条不符合就直接退出。

这样的话就会有两个问题：

1.当前的元素对比下一个元素并不是大于关系就退出了之后，我们的删除次数可能没有用完，所以在外面继续出栈，直到删除次数用完。

2.我们并没有处理前导0。所以这就需要我们额外处理一个前导0.这也是作者需要学习的地方。

处理的时候我们需要有一个flag标志变量判断当前是不是连续的0，如果判断当前并不是连续的0中的其中一个，我们就把这个标志变成false。这样就不会出现删除除前导0以外的0了。

class Solution {
public:
    string removeKdigits(string num, int k) {
        vector<char>stack;
        for(int i=0;i<num.size();i++){
            while(!stack.empty()&&stack.back()>num[i]&&k>0){
                stack.pop_back();//这个时候也就是说栈不空，并且当前元素大于下一个元素，且删除次数没有用完
                k--;
            }
            stack.push_back(num[i]);//在不满足上面的循环条件的时候就进栈
        }
        for(;k>0;k--)
        stack.pop_back();//删除次数可能没有用完就退出了，所以需要判断一下，没有删完就继续删
        string res;
        bool flag=true;
        for(int i=0;i<stack.size();i++){//前导0的判断
            if(flag&&stack[i]=='0')
            continue;
            else{
                flag=false;
                res+=stack[i];
            }
        }
        return res==""?"0":res;
    }
};