题目描述

难度分:$1500$

输入$T(\leq 10^5)$表示$T$组数据。所有字符串长度之和$\leq 5 \times 10^5$。

每组数据输入一个长度$\leq 5 \times 10^5$的数字字符串$s$，和$k(1 \leq k \lt len(s))$。

$s$是一个不含前导零的正整数。

你需要删除$s$中的恰好$k$个字符，使得剩余字符的字典序最小，并且是没有前导零的正整数。

输入样例

5
10000
4
1337
0
987654321
6
66837494128
5
7808652
3

输出样例

1
1337
321
344128
7052

算法

单调栈

这个题比较容易想到单调栈的做法，如果没有“不能包含前导零”的限制，那就遍历字符串$s$，在满足“栈顶数字大于当前数字$s[i]$，还可以删除数字”这两个条件的情况下弹栈，否则直接把$s[i]$压栈。

但是多了一个“不能包含前导零”的限制就比较讨厌，因为有可能会把栈弹空，然后压进去一个$0$。此时我们可以思考一个极端的例子前$k$个数字全部删掉才是最优解，也就是说最优解保留了后$n-k$个数字，首字符就是$s[k+1]$。而其他更一般的情况，一定满足最优解的首字符在$[1,k+1]$这个区间内，否则删除字符数一定超过$k$。所以我们找到子串$[1,k+1]$中最小的非零数字$s[j]$，强制保留它作为首个字符，然后在子串$[j+1,n]$上跑单调栈，在弹栈时保证栈中至少有两个元素就可以了。

由于cpp的字符串有弹出尾字符的方法，直接把答案串当成栈用即可。为了确保答案串的长度为$n-k$，最后记得把栈顶多余的字符弹出。

复杂度分析

时间复杂度

遍历一遍字符串$s$执行单调栈算法，时间复杂度为$O(n)$。

空间复杂度

空间消耗主要就是“栈”所开辟的空间，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 500010;
char s[N];
int t, k;

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        scanf("%d", &k);
        string ans;
        int j = 1;
        for(int i = 1; i <= k + 1; i++) {
            if(s[i] > '0' && s[i] < s[j]) {
                j = i;
            }
        }
        k -= j - 1;
        ans.push_back(s[j]);
        for(int i = j + 1; i <= n; i++) {
            while(ans.size() > 1 && ans.back() > s[i] && k > 0) {
                ans.pop_back();
                k--;
            }
            ans.push_back(s[i]);
        }
        while(k > 0) {
            ans.pop_back();
            k--;
        }
        cout << ans << endl;
    }
    return 0;
}