删除 K 位数字得到最小数为什么用单调栈？

简化版

删除 K 位数字得到最小数，要让高位尽量小。遍历数字时维护单调递增栈：当前数字比栈顶小且还能删除时，弹出栈顶；最后如果 K 还没用完，从尾部删除。结果去掉前导零，空串返回 0。

详细版

高位对数值影响最大，因此一旦出现更小的当前数字，就应该优先删除它前面更大的高位数字。例如 1432219, k=3，删除 4、3、2 后得到 1219。

String removeKdigits(String num, int k) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : num.toCharArray()) {
        while (k > 0 && !stack.isEmpty() && stack.peekLast() > c) {
            stack.pollLast();
            k--;
        }
        stack.offerLast(c);
    }
    while (k > 0 && !stack.isEmpty()) {
        stack.pollLast();
        k--;
    }
    StringBuilder sb = new StringBuilder();
    boolean leadingZero = true;
    for (char c : stack) {
        if (leadingZero && c == '0') continue;
        leadingZero = false;
        sb.append(c);
    }
    return sb.length() == 0 ? "0" : sb.toString();
}

这是单调栈和贪心结合的典型题：保持结果前缀尽量小。

完整版教学

一、为什么要优先处理高位

十进制数字中，高位的影响远大于低位。对 98765 删除 1 位，删 9 得到 8765，远小于删 5 得到 9876。所以当扫描到一个更小数字时，如果前面的高位更大，就应优先删除前面的高位。

1432219, k=3
看到 3 时，前面的 4 更大，删 4
看到 2 时，前面的 3 更大，删 3
后续再删一个 2
结果 1219

这就是单调递增栈背后的贪心逻辑。

二、单调递增栈的不变量

栈中保存当前构造出的最优前缀，并尽量保持从左到右递增。当当前字符 c 小于栈顶时，栈顶是一个更靠前且更大的数字，删除它能让结果字典序变小。只要还有删除额度，就持续弹出。

这个过程不是为了让最终所有数字完全递增，而是在可删除次数限制下，让每个前缀尽量小。因为一旦数字进入更高位，后面再小的数字也很难弥补高位过大的损失。

三、为什么最后还要从尾部删除

如果原数字本身单调递增，例如 123456, k=2，扫描过程中不会触发弹栈。但仍然必须删除 2 位。此时删除末尾最大、最低价值的数字最优，得到 1234。

数字形态	扫描中会弹吗	剩余 k 怎么办
递减，如 `54321`	会大量弹	通常很快用完
递增，如 `12345`	不会弹	从尾部删
有波动，如 `1432219`	局部弹	可能还要尾删

尾删是贪心逻辑的补充：前缀已无法改善，就牺牲低位。

四、前导零怎么处理

删除后可能出现前导零，例如 10200, k=1 删除 1 后得到 0200，规范答案应是 200。因此构造结果时要跳过开头的零。如果全被跳过，说明结果数值是 0。

num = "10", k = 2
栈最终为空 -> 返回 "0"

num = "100200", k = 1
删除 1 -> "00200" -> 去前导零 -> "200"

注意中间的零不能删除，例如 2001 中两个零是有效数字。

五、复杂度和实现选择

使用 ArrayDeque<Character> 支持尾部入栈和弹栈。每个字符最多入栈一次、出栈一次，时间复杂度 O(n)。结果构造再遍历一次栈，总体仍是 O(n)，额外空间 O(n)。

总入栈 <= n
总出栈 <= k <= n
总复杂度 O(n)

如果用字符串频繁删除中间字符，可能退化到 O(n²)，因为每次删除都要移动后续字符。

六、常见误区与追问

记忆钩子：想让数最小，先让高位小。当前数字更小，就把前面挡路的大数字删掉。

误区：删除全局最大的 K 个数字。 位置很重要，删低位大数不一定比删高位稍大的数更优。
误区：忘记处理剩余 k。 单调递增输入不会触发弹栈，必须从尾部补删。
误区：把所有零都删掉。 只删除前导零，中间零可能决定数值大小。
追问：为什么用 > 而不是 >=？ 相等时保留前面的数字通常更稳，删除后面的相等数字不会让前缀变大。
追问：结果为空为什么返回 0？ 删除所有数字或只剩前导零时，数值意义就是 0。
追问：这题是栈还是贪心？ 两者都是；贪心决定删除策略，栈高效维护可回退的前缀。

七、加强记忆

删除 K 位数字的口诀是：高位优先，小数顶掉大数，删不够就删尾，最后去前导零。单调递增栈维护当前最优前缀，k 是还能反悔删除的次数。理解“当前更小数字会让前缀变小”，就能解释为什么这套贪心正确。

简化版

详细版