移掉 K 位数字如何用贪心单调栈得到最小数？

简化版

移掉 K 位数字的贪心原则是：越靠前的高位越重要，只要当前数字比栈顶小，并且还可以删除，就删除栈顶，让更小的数字提前。最后如果还没删够，就从末尾继续删，再去掉前导零。

详细版

把结果看成一个单调递增趋势的栈。遍历数字字符 c，当 stack 非空、k > 0 且 stack.peek() > c 时，弹出栈顶，因为用当前更小的 c 替换前面的较大数字，会让整体数值更小。之后把 c 入栈。

遍历结束后，如果 k 仍大于 0，说明原数字整体已经递增，此时只能从尾部删除。构造答案时去掉前导零；如果结果为空，返回 "0"。时间复杂度 O(n)，空间复杂度 O(n)。

完整版教学

一、为什么高位优先决定大小

十进制数字比较大小时，越靠左的位权越大。比如 1432 和 1322，只看第二位就能判断 1322 更小，因为百位从 4 变成了 3，后面个位十位再怎么变化都很难抵消这个影响。

1432
1322
 ^  这里 4 > 3，所以第二个更小

因此这题的贪心核心不是“删最大的数字”，而是“在尽可能靠前的位置删掉破坏变小机会的较大数字”。

二、为什么遇到更小数字要弹出前面的大数字

假设栈顶是 4，当前字符是 3，并且还能删除。把 4 留在前面会让结果前缀更大；删除 4 让 3 提前，得到的数一定不差。

局部选择	结果趋势
保留前面的 `4`	高位较大
删除 `4`，让 `3` 前移	高位变小

记忆钩子：这题不是找全局最大位删除，而是维护“前缀尽量小”。

这个交换理由是贪心正确性的来源：一旦当前位置能用更小数字替换前面的较大数字，就应该马上做。

三、单调栈状态怎么维护

栈里保存当前构造出的结果前缀。遍历每个字符 c：

while 栈非空 && k > 0 && 栈顶 > c:
    弹出栈顶，k--
把 c 入栈

这样做会让栈尽量保持从左到右不下降。不是绝对严格递增，因为当 k 用完后，后续字符只能全部保留。

num = 1432219, k = 3
读到 3 时弹出 4
读到 2 时弹出 3
再读到 2 时弹出前一个 2? 不弹，因为相等不需要删

相等时不弹，通常能保留更靠前的数字，给后面更多删除机会。

四、为什么递增数字要从末尾删

如果遍历完后 k 还没用完，说明栈中没有出现“前大后小”的机会，数字整体类似递增。此时删除越靠后的数字，对高位影响越小，结果最小。

num = 123456, k = 2
删前面：3456 或 12456 之类会明显变大
删后面：1234 最小

公式化地看，前缀越短且越保留小数字，整体越小。因此剩余删除次数应该从栈尾消耗。

五、代码模板

String removeKdigits(String num, int k) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : num.toCharArray()) {
        while (!stack.isEmpty() && k > 0 && stack.peekLast() > c) {
            stack.pollLast();
            k--;
        }
        stack.addLast(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();
}

这里用 ArrayDeque 比 Stack 更现代。注意最后去前导零，不要在入栈时随便跳过 0，因为中间的 0 可能是最优结果的一部分。

六、用例子完整推演

num="1432219", k=3：

读 1：栈 [1]
读 4：栈 [1,4]
读 3：弹 4，栈 [1,3]，k=2
读 2：弹 3，栈 [1,2]，k=1
读 2：相等不弹，栈 [1,2,2]
读 1：弹 2，栈 [1,2,1]，k=0
读 9：栈 [1,2,1,9]

结果是 1219。每一次弹出都发生在“当前位能让更小数字提前”的瞬间。

七、常见误区与追问

误区：每次删除当前最大的数字。 最大数字如果在低位，删除它未必比删除高位较大数字更优。
误区：相等数字也弹出。 相等时弹出不会让当前位更小，还可能浪费删除次数。
误区：入栈时直接丢弃所有 0。 只有前导零需要去掉，中间的 0 可能非常关键。
追问：为什么栈是单调递增趋势？ 因为一旦前面数字大于后面数字，就优先删除前面的大数字。
追问：如果 k 等于数字长度怎么办？ 最终栈为空，返回 "0"。
追问：复杂度为什么是 O(n)？ 每个字符最多入栈一次、出栈一次。

八、加强记忆

移掉 K 位数字记成“高位越小越好”。遍历时只要当前数字能打败前面的栈顶，就把栈顶删掉；删不动了再入栈。遍历完还没删够，说明没有下降机会，只能从末尾删。最后别忘了前导零和空串返回 0，这两个边界经常扣分。

简化版

详细版