题目链接：AcWing 1453. 移掉K位数字

一、题解

题目大意：

给定一个很长的字符串表示的非负整数，去掉 k 位数，使得结果表示的数最小！

思路：

对于一个单调递增的序列，我们发现，若出现后一个数比序列尾的数要小，即发生了逆序，那么我们应该尽可能删掉该序列的末尾比出现的数大的数，这样可以使得结果尽可能的小！

删完后，将当前数加入序列！

当然可以删除的前提是还有次数可以删！

最后处理完毕，若还有删除次数，则此时的单调递增序列，可以直接删掉后面对应个数的数即可！

注意：

为了防止全部删完，我们提前在最前方插入一个0，最终我们将前导0去掉即可！

时间复杂度： O(n)

空间复杂度： O(n)

二、AC代码

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int main(){
    string s; int k;
    cin >> s >> k;
    string res = "0";
    for(auto c : s){
        while(k && res.back() > c) res.pop_back(), k --;
        res += c;
    }
    while(k --) res.pop_back();
    k = 0;
    while(k + 1 < res.size() && res[k] == '0') k ++;
    cout << res.substr(k);
    return 0;
}