每日一题~ 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;
 } 

原文地址：https://blog.csdn.net/x1653673086/article/details/140224955

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！