社区讨论

单调栈优化

P1106删数问题参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mln798tf
此快照首次捕获于
2026/02/15 11:42
4 天前
此快照最后确认于
2026/02/15 11:57
4 天前
查看原帖
本题用贪心+单调栈优化,复杂度O(n)
CPP
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string num,res="";
    int s,pl=0;
    cin>>num>>s;
    for(char c : num){
        while(s>0&&!res.empty()&&res.back()>c){
            res.pop_back();
            s--;
        }
        res.push_back(c);
    }
    //------------------------
    while(s>0&&!res.empty()){
        res.pop_back();
        s--;
    }
    while(pl<res.size()-1&&res[pl]=='0'){
        pl++;
    }
    for(int i=pl;i<res.size();i++){
        cout<<res[i];
    }
    return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...