用单调栈从左到右删除更大的前一位，使剩余数字的字典序尽量小，最后去掉输出前导零。
OJ: luogu
题目 ID: P1106
难度:普及-
标签:贪心单调栈字符串python
日期: 2026-07-15 21:51
题意
给定一个不超过 250 位的正整数和一个整数 k，删除其中恰好 k 个数字，剩下数字的相对顺序不变。要求输出能得到的最小非负整数，输出时不能带前导零。
思路
要让数字尽量小，越靠前的位置越重要。扫描到一个新数字 digit 时，如果它比已经保留的最后一位更小，那么删除前面那个较大的数字，可以让结果的更高位变小，答案一定不会变差。
这正好是单调栈：
- 从左到右扫描每个数字；
- 当还可以删除，并且栈顶数字大于当前数字时，弹出栈顶；
- 把当前数字压入栈；
- 如果扫描结束后还没删够，说明剩余数字已经单调不降，就从末尾删掉多余的位；
- 拼接结果并去掉前导零，若为空则输出
0。
例如 175438 删除 4 位：
| 扫描数字 | 操作后的栈 | 剩余删除次数 |
|---|---|---|
1 |
1 |
4 |
7 |
17 |
4 |
5 |
15 |
3 |
4 |
14 |
2 |
3 |
13 |
1 |
8 |
138 |
1 |
最后还要删一位，从末尾删掉 8，得到 13。
Python 知识
- 字符串可以直接逐字符遍历，数字字符的大小关系与真实数字大小一致。
- 列表用作栈：
append入栈，pop出栈。 "".join(stack).lstrip("0")先拼接字符列表，再删除输出前导零。
这题不适合把原数转成整数处理，因为题目关心“删除数字并保留相对顺序”。
代码
python
def main():
number = input().strip()
k = int(input())
stack = []
for digit in number:
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
if k > 0:
stack = stack[:-k]
answer = "".join(stack).lstrip("0")
print(answer if answer else "0")
if __name__ == "__main__":
main()cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-27 00:00
* update_at: 2026-07-27 00:00
*/
/* P1106 删数问题 */
/* 从左到右扫描，如果当前数字比栈顶小，就删除栈顶（贪心：让高位尽量小）。 */
#include <bits/stdc++.h>
using namespace std;
const int MAXL = 255;
char s[MAXL];
int k;
char stk[MAXL]; // 字符栈
int top = 0; // 栈顶指针
int main() {
cin >> s >> k;
int len = strlen(s);
// 单调栈：尽量让前面的数字小
for (int i = 0; i < len; i++) {
// 还可以删除，且栈顶比当前数字大，就弹出栈顶
while (k > 0 && top > 0 && stk[top] > s[i]) {
top--;
k--;
}
stk[++top] = s[i];
}
// 如果还没删够，从末尾删
top -= k;
// 去掉前导零
int start = 1;
while (start <= top && stk[start] == '0') start++;
if (start > top) {
cout << "0\n";
} else {
for (int i = start; i <= top; i++) {
cout << stk[i];
}
cout << "\n";
}
return 0;
}复杂度
每个数字最多入栈一次、出栈一次，时间复杂度是 L 是数字长度。
空间复杂度是
总结
删除数字类最小化问题常看“高位能不能变小”。只要当前数字能替换掉前面更大的高位，就应该立刻删除那个更大的数字。