LeetCode 402. 移掉 K 位数字

约 5 分钟
文章信息 14 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 50-100 腾讯 字节 华为 微软 亚马逊 百度 虾皮 猿辅导
标签
字符串 栈 贪心 单调栈

题目描述

✅ 402. 移掉 K 位数字

image-20260928195002546

题意分析

从十进制数字字符串 num 中恰好删除 k 个字符，让剩余字符表示的非负整数尽可能小。只能删除，不能交换或重新排序，因此保留下来的字符必须维持原来的相对顺序。

设原长度为 n，删除完成后先保留 n - k 个字符，再去掉前导零作为输出格式整理；去前导零不占删除额度。若全部字符都被删除，或者剩余字符全是零，返回 "0"。字符串最长可达 10^5 位，需要直接按字符处理。

解法：单调栈构造最小数字

核心思路

[!blue]

所有候选结果在去前导零之前长度都相同，数值大小由最靠左的不同数字决定。因此，删除时应优先改善高位，而不是只考虑删掉整个字符串中数值最大的字符。

从左到右扫描，用栈保存暂时保留的数字。如果栈顶大于当前数字，且还有删除额度，就删除栈顶，让更小的当前数字向前靠。这会降低最早发生变化的位置，后面的数字再大也无法抵消这个高位优势。弹出后，新栈顶也可能比当前数字大，因此必须持续比较，而不是只删除一次。

栈顶与当前数字相等时，删掉前者不会改善这一位，却会消耗可以留给后面更大数字的额度，所以只在严格大于时弹栈。只要删除额度没有用完，栈内数字就保持非递减；额度耗尽后，后续字符必须全部保留，此时不再强求整个栈有序。

扫描结束若仍有删除额度，说明保留序列已经非递减，没有可以通过删除下降处来改善的高位。此时从末尾删最合适：删除前面的较小数字只会让后面不更小的数字提前，无法得到更小结果。

扫描中的弹栈和最后的删尾合计恰好消耗原来的 k 次删除。随后才跳过前导零；如果没有有效数字，统一返回 "0"。这样选取最小子序列与输出格式处理各自独立，不会把前导零误算成额外删除。

解题步骤

  1. 创建字符栈，从左到右读取当前数字 ch。
  2. 当剩余 k > 0、栈非空且栈顶大于 ch 时，反复弹出栈顶，并将 k 减一。
  3. 把当前数字压入栈中；删除额度耗尽后，继续按原顺序保留后面的数字。
  4. 扫描结束后，从栈尾再删除剩余的 k 个字符。
  5. 跳过栈中的前导零，将余下字符作为结果；若余下部分为空，返回 "0"。

代码实现

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:])
}

复杂度分析

设字符串长度为 $n$。

  • 时间复杂度：$O(n)$。虽然扫描中嵌套了弹栈循环，每个字符仍只入栈一次、最多出栈一次；去前导零和构造结果也只需线性时间。
  • 辅助空间复杂度：$O(n)$，用于保存暂时保留的数字。

关键点总结

[!green]

  • 固定长度的数字串优先比较高位，遇到较小数字时应优先淘汰它前面的较大数字。
  • 单调性只在还有删除额度时维护，额度耗尽后不能再弹栈。
  • 剩余额度从末尾消耗，完成恰好删除后再去前导零。

易错点总结

[!yellow]

  • 弹栈只用 if，会漏掉一个小数字能够连续替代的多个较大前置数字，应使用循环。
  • 比较条件写成 >=，会在相等数字上提前浪费删除额度，可能无力删除后续真正更大的数字。
  • 扫描结束忘记删去剩余额度，会得到长度超过要求的结果，尤其是在原序列非递减时。
  • 在贪心扫描中忽略零却没有同步维护删除计数，会混淆“删除字符”和“省略前导零”两件事。
  • 全部删空或只剩零时应返回 "0"；不能直接返回空字符串，也不能把长字符串转换成普通整数。

相似题目

题目 难度 关联与区别
316. 去除重复字母 中等 同样用单调栈弹出不利前缀，本题由删除次数限制弹栈；316要求原串每种字母恰好保留一次，既要判重，又要确认被弹字母之后还能补回。
321. 拼接最大数 困难 固定长度最优子序列的选取相同，原题取最大并需合并两条来源。
1081. 不同字符的最小子序列 中等 保持单调候选并在后续仍可补足时弹出较差元素；本题删除固定数量的较大前缀数字，该题选择每种不同字符一次的最小字典序子序列。
1673. 找出最具竞争力的子序列 中等 保持单调候选并在后续仍可补足时弹出较差元素；本题删除固定数量的较大前缀数字，该题保留固定长度的最具竞争力子序列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/70730153
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！