本文主要是介绍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";elsereturn 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;}
};这篇关于leetcode 402.移掉k位数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
