LeetCode 402. 移掉 K 位数字
目录
题目描述
题意分析
给定用字符串表示的非负整数
num和整数k，从中恰好移除k位数字（不是至多），使剩下的数字按原有相对顺序拼起来最小，以字符串形式返回。「保持相对顺序」意味着这是在选一个长度为
n - k的子序列，而不是任意重排；比较的是数值大小，但由于剩余长度固定，数值比较可以退化为字符串的字典序比较。约束信号：
num长度可达 $10^5$，逐个枚举删哪k位的组合数是天文数字，必须线性或近线性解决；num不含前导零，但删除之后剩余串可能以0开头。边界：结果若有前导零要去掉（
"10200"删 1 位得"0200"，应输出"200"）；k等于长度时所有位都被删光，以及去零后为空串的情形，都要返回"0"而不是空字符串。
解法：单调栈构造最小数字
核心思路
问题关键：删除后保留的是长度固定为
n - k的子序列。长度相同时，数值越小等价于字典序越小，因此越高位的数字越值得优先优化。为什么选单调栈：扫描到更小的数字时，如果前面紧邻保留的数字更大，删除这个较大的栈顶就能让当前数字提前一位，结果一定更小。栈允许从末尾连续反悔：只要还有删除额度且栈顶大于当前数字，就弹出栈顶；每个字符最多进出栈一次。
不变量与正确性：处理每个字符后，栈中保留原相对顺序，并且在还有删除额度时不存在可继续消除的降序栈顶。弹掉较大的高位、换成当前较小数字，会得到同长度但字典序更小的前缀，因此最优解不会需要被弹出的字符。若扫描结束仍有额度，说明栈整体非递减，此时删除越靠后的数字影响越小，应从尾部删除。最后再统一去掉前导零。
解题步骤
- 用字符数组或
StringBuilder充当栈，从左到右扫描数字。- 当
k > 0且栈顶大于当前字符时持续弹栈，并减少删除额度；必须用while，因为一个小数字可能连续淘汰多个高位大数字。- 将当前字符入栈，继续处理后续位置。
- 扫描结束若
k > 0，直接从栈尾截掉k位，保证恰好删除指定数量。- 跳过结果的前导零；若全部删空或只剩零，返回
"0"。"1432219"、k = 3中依次弹掉4、3、2，栈最终为"1219"；"10200"、k = 1得到"0200"，规范化后返回"200"。
代码实现
class Solution {
public String removeKdigits(String num, int k) {
StringBuilder stack = new StringBuilder();
for (int i = 0; i < num.length(); i++) {
char ch = num.charAt(i);
while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > ch) {
stack.deleteCharAt(stack.length() - 1);
k--;
}
stack.append(ch);
}
stack.setLength(stack.length() - k);
int idx = 0;
while (idx < stack.length() && stack.charAt(idx) == '0') {
idx++;
}
String res = stack.substring(idx);
return res.length() == 0 ? "0" : res;
}
}
func removeKdigits(num string, k int) string {
stack := make([]byte, 0, len(num))
for i := 0; i < len(num); i++ {
ch := num[i]
for k > 0 && len(stack) > 0 && stack[len(stack)-1] > ch {
stack = stack[:len(stack)-1]
k--
}
stack = append(stack, ch)
}
stack = stack[:len(stack)-k]
idx := 0
for idx < len(stack) && stack[idx] == '0' {
idx++
}
if idx == len(stack) {
return "0"
}
return string(stack[idx:])
}
复杂度分析
- 时间复杂度：$O(n)$。每个字符入栈一次、最多出栈一次，去前导零也只扫描一次。
- 空间复杂度：$O(n)$，用于保存单调栈。
关键点总结
- 定长子序列比较大小时，先出现的不同数字决定结果，所以优先优化高位。
- 弹栈条件必须同时满足：还有额度、栈非空、栈顶严格大于当前数字。
- 扫描后剩余额度要从尾部消耗，否则没有做到“恰好删除
k位”。- 构造结果与规范化输出分开处理：先完成贪心，再去前导零并处理空串。
易错点总结
- 漏删剩余额度：
"112"、k = 1全程不会弹栈，最后必须删尾得到"11"。- 弹栈条件写成
>=："112"、k = 1会过早删掉相等的1，得到较大的"12"。- 只用
if弹一次："1230"、k = 3中字符0需要连续弹掉3、2、1；只弹一次会错误保留高位。- 忘记前导零和空串：
"10200"、k = 1应返回"200"；全部删完时应返回"0"。- 转换成整数处理：
num最长可达 $10^5$，任何整数类型都会溢出，应始终按字符操作。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 316. 去除重复字母 | 中等 | 单调栈 + 剩余计数：删除量不定，字符不能重复且必须都出现 |
| 1081. 不同字符的最小子序列 | 中等 | 与 316 完全同题，换题面验证同一套栈贪心 |
| 1673. 找出最具竞争力的子序列 | 中等 | 本题的数组版：保留恰好 k 个元素，配额换算方向相反 |
| 321. 拼接最大数 | 困难 | 两个数组各取子序列后归并求最大，单调栈作为子过程复用 |
| 456. 132 模式 | 中等 | 单调栈找结构模式而非构造子序列，栈的单调方向相反 |
| 739. 每日温度 | 中等 | 单调栈入门：求下一个更大元素的距离，无贪心构造成分 |