每日一题~ leetcode 402 (贪心+单调栈)

click me!

这个贪心的推导在leetcode上已经很明确了。
click me!
删除k个数，可以先考虑删除一个数。这也是一种常见的思路。（如果进行同样的操作多次，可以先只 考虑一次操作如何实现，或者他的影响。完成这一次操作后，剩下的问题会成为 新的子问题。用相同的策略 去 做就可以了。）
删去一个字符后，剩下的 n−1 长度的数字序列就形成了新的子问题，可以继续使用同样的策略，直至删除 k 次。

#include<bits/stdc++.h>
using namespace std;int main()
{string s;cin>>s;int k;cin>>k;stack<char>a; a.push(s[0]);for (int i=1;i<s.size();i++){char t=s[i];if (t>=a.top()){a.push(t); }else {while(!a.empty()&&k>0&&t<a.top()){k--;a.pop();}a.push(t);}}if (k){while(k--){a.pop();}}vector<char>ans;while(!a.empty()){char i=a.top();ans.push_back(i);a.pop();}//删除前导零reverse(ans.begin(),ans.end()) ;int tot=0;while(ans[tot]=='0'&&tot+1<ans.size()){tot++;}for (int i=tot;i<ans.size();i++)cout<<ans[i];cout<<endl;return 0;}