#402. 移掉 K 位数字

• LeetCode：402. 移掉 K 位数字
• 难度：中等
• 归类：贪心、字符串、单调栈
• 主解法：单调递增栈构造最小子序列

#先给结论

删除 k 位后，剩余数字的相对顺序不能改变，而且剩余长度固定为 num.length - k。因此问题等价于：

从 num 中选出长度为 num.length - k 的、字典序最小的数字子序列。

最直观的思路是反复找"左边比右边大"的位置并删掉左边那位；把它优化成一次遍历，就是单调栈。

从左到右扫描数字。只要当前数字比栈顶更小，并且还有删除次数，就删除栈顶：

while (remainingRemovals > 0 && stack.top > current) {
    pop stack.top
}

把更小的数字尽量放到更高位，会让结果变小。如果扫描结束后仍有删除次数，说明栈已经整体非递减，此时从末尾删除最大的高位次最低的数字即可。

最后只做结果格式化：去掉前导零；如果结果为空，则返回 "0"。

#题目描述

给定一个用字符串表示的非负整数 num 和整数 k，恰好移除其中 k 位数字，使剩下的数字最小，并以字符串形式返回结果。

示例 1：

输入：num = "1432219", k = 3
输出："1219"

示例 2：

输入：num = "10200", k = 1
输出："200"

删除首位 "1" 后得到 "0200"，返回时去掉前导零。

示例 3：

输入：num = "10", k = 2
输出："0"

题目约束：

• 1 <= k <= num.length <= 10^5。
• num 只包含数字。
• 除了 "0" 本身，输入没有前导零。
• 必须恰好删除 k 位，而不是最多删除 k 位。

#直观理解：排队踢人

把 num 里的每个数字想象成一个人的"身价"，你要保留 n - k 个人排成一队，让最终组成的数字最小。

从左往右看人：

• 当前来了一个新人（digit），如果前面的人（栈顶）比他更贵（stack.top > digit），而你还剩踢人名额（remainingRemovals > 0），就把前面贵的踢掉。
• 因为高位越小，整个数字就越小。让便宜的人站前面，结果一定更好。
• 前面的人和新人一样便宜或更便宜？那就别踢，留着。

走完一轮，如果还有踢人名额，说明队伍已经是越来越贵（非递减）的了。那只能从队尾开始踢——踢最贵的、位置最靠后的。

最后去掉前导零即可。

#好懂但慢的版本：逐轮找下降点

如果你完全不想用栈，可以每轮都从头扫描，找到第一个左边比右边大的位置，删掉左边那个，重复 k 次：

"1432219", k=3

第1轮：1 < 4 > 3 ↓  发现 4>3，删 4 → "132219"
第2轮：1 < 3 > 2 ↓  发现 3>2，删 3 → "12219"
第3轮：1 < 2 = 2 > 1 ↓  发现 2>1，删 2 → "1219"

这个思路非常好懂，而且结果正确。但每次删除都可能重新扫描和复制字符串，时间复杂度是 O(kn)。当 n = 10^5 时会超时，无法通过。

#为什么单调栈就是它的加速版

逐轮找下降点的核心操作是：遇到 左边 > 右边 时，删掉左边那位。

单调栈做的其实是同一件事，只是把所有轮次的扫描压缩成一次遍历：

• 用栈保留当前已经确定的人选。
• 当新人到来时，直接在栈顶回溯检查前面最近的人是否更贵。
• 如果更贵就踢掉（pop），然后继续检查新的栈顶。

这样不需要每轮重新扫描整个字符串，每个数字最多入栈一次、出栈一次，总时间降到 O(n)。

#贪心选择

假设已经扫描到当前数字 digit，栈顶数字为 top。

#top > digit

如果还有删除次数，删除 top 比删除 digit 或更右侧的数字更优：

• 删除 top 后，较小的 digit 可以提前到更高位。
• 如果保留 top，结果在这个更早的位置就是较大的数字。
• 数字高位的差异优先于后面所有位置，因此应立即删除 top。

弹出一次后，新栈顶可能仍大于 digit，所以要使用 while 连续删除。

#top <= digit

此时不能为了当前数字删除栈顶：

• 如果 top < digit，保留更小的高位显然更优。
• 如果 top === digit，删除前一个相等数字不能改善当前高位，反而会浪费删除机会。

因此弹栈条件必须是严格大于，不能写成 >=。

#单调栈状态与不变量

维护：

• stack：当前已经扫描前缀经过贪心删除后保留下来的数字。
• remainingRemovals：还必须删除的位数。

当 remainingRemovals > 0 时，当前数字会不断消除栈尾的逆序对，所以栈尽量保持非递减。更准确地说：

• 只要还有删除额度，栈顶大于当前数字的情况就会立即被消除。
• 删除额度耗尽后，后续数字只能原样追加，栈不再保证单调。
• 栈中数字始终保持它们在原字符串中的相对顺序。

stack 既是单调栈，也是最终答案的构造缓冲区。

#为什么扫描结束后从末尾补删

如果扫描完整个字符串后 remainingRemovals > 0，说明在还有删除额度时，没有再遇到能触发 stack.top > digit 的下降位置。此时保留序列是非递减的。

例如：

num = "12345", k = 2

扫描期间不会弹栈。对于非递减序列：

• 删除中间或前面的数字，会让一个相同或更大的数字提前到更高位。
• 删除末尾数字不改变此前所有高位。

所以应依次删除末尾的 "5"、"4"，得到 "123"。

#示例推演

以 num = "1432219"、k = 3 为例：

最终不需要补删，也没有前导零，答案为 "1219"。

再看 num = "10200"、k = 1：

读到 0 时删除前面的 1，栈最终为 "0200"
格式化时去掉前导零，得到 "200"

#代码实现

思路参考：JoshCrozier/leetcode-javascript。本文重新整理了变量命名，并补充贪心证明、末尾补删与前导零处理；原项目采用 MIT License。

#JavaScript 实现

/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function (num, k) {
    const stack = [];
    let remainingRemovals = k;

    for (const digit of num) {
        while (
            remainingRemovals > 0 &&
            stack.length > 0 &&
            stack[stack.length - 1] > digit
        ) {
            stack.pop();
            remainingRemovals--;
        }

        stack.push(digit);
    }

    while (remainingRemovals > 0) {
        stack.pop();
        remainingRemovals--;
    }

    const result = stack.join('').replace(/^0+/, '');
    return result || '0';
};

#更简洁的 slice 写法

如果不喜欢第二个 while 循环，可以用 slice 直接从末尾截掉剩余删除次数：

var removeKdigits = function (num, k) {
    const stack = [];
    let remaining = k;

    for (const digit of num) {
        while (remaining > 0 && stack.length && stack.at(-1) > digit) {
            stack.pop();
            remaining--;
        }
        stack.push(digit);
    }

    const result = stack.slice(0, stack.length - remaining).join('');
    return result.replace(/^0+/, '') || '0';
};

两种写法逻辑完全一致，只是末尾补删的方式不同。

需要注意的是，slice 不是去掉"不合法"的值，而是去掉"多余的长度"。主循环里每个数字都会入栈一次；如果扫描完整个字符串后 remaining 还有剩余，说明栈里保留下来的数字比目标长度 num.length - k 多了 remaining 个。此时序列已经是非递减的，末尾的数字影响最小，所以直接从末尾截掉剩余次数即可。

#代码与思路对照

#正确性说明

可以从局部交换和剩余删除两部分证明。

#扫描过程中的弹栈是安全的

当 top > digit 且还有删除次数时，考虑任何保留 top、却删除 digit 或更右侧数字的方案。把该方案改成删除 top 并保留 digit，删除数量不变，数字相对顺序仍合法。

两个结果在更靠左的位置首次产生差异：修改后的方案放入较小的 digit，所以一定更小。因此最优方案无需保留这个 top，弹栈不会漏掉最优答案。

连续应用这一交换，就能安全地删除所有位于当前 digit 左侧、且应该让位给它的较大栈顶。

#剩余次数从末尾删除是安全的

如果扫描结束仍有删除次数，当前保留序列非递减。删除任意非末尾数字都会让其右侧一个不小于它的数字提前；删除末尾则保留最长的原有最小前缀。因此每一步删除末尾都不会比删除更靠前的位置差。

算法总共恰好执行 k 次删除，留下的又是所有合法子序列中字典序最小的一个。去除前导零只改变输出格式，不改变数值，所以最终答案正确。

#边界与陷阱

• k === num.length： 所有数字都被删除，返回 "0"。
• 输入非递减： "12345" 不会在扫描时弹栈，必须从末尾补删。
• 连续下降： "54321" 中一个较小数字可能连续触发多次弹栈，所以必须使用 while。
• 相等数字： 条件应为 top > digit，不能写成 top >= digit。例如 "112"、k = 1 的最优结果是 "11"。
• 前导零： "10200" 删除 "1" 后先得到 "0200"，再格式化为 "200"。
• 全零结果： "1000"、k = 1 格式化后为空，应返回 "0"。
• 恰好删除 k 位： 前导零的清理不是删除操作，不能用它代替剩余删除次数。
• 字符比较： 输入只包含单个十进制数字，字符 '0'～'9' 的字典序与数值顺序一致，无需反复转换为 Number。
• 不要用 shift()： 栈只在尾部执行 push() 和 pop()，才能保持摊还常数操作。

#复杂度分析

设 n = num.length：

• 每个数字入栈一次，最多出栈一次，因此所有弹栈循环合计为 O(n)。
• join() 和清理前导零也都是 O(n)。
• 时间复杂度：O(n)。
• 空间复杂度：O(n)，用于单调栈和最终字符串。

虽然代码中存在嵌套的 while，但它不会让时间复杂度变成 O(n²)，因为一次入栈的数字最多只会被弹出一次。

#替代解法

#每轮删除第一个下降位置

每次从左到右寻找第一个满足 num[i] > num[i + 1] 的位置并删除 num[i]；如果不存在下降位置，就删除末尾。重复 k 次也能得到正确答案。

这个过程与单调栈的贪心选择相同，但每次删除都可能重新扫描和复制字符串，时间复杂度可达 O(kn)，无法适应 10^5 的输入长度。

#枚举保留子序列

可以枚举所有长度为 n - k 的子序列并取最小值，但候选数量为组合数：

C(n, n - k)

只适用于极小输入，可作为测试时的暴力对拍算法。

#面试官递进追问

#1. 为什么本题适合单调栈？

当前较小数字到来时，需要删除它左侧最近的较大保留数字，而且一次删除后还要继续检查新的栈顶。这种"从末尾反复撤销之前选择"的过程正适合栈。

#2. 为什么删除左侧较大数字一定更优？

它能让当前较小数字提前到更高位。两个等长结果的大小由第一个不同位置决定，所以高位变小带来的收益无法被后面的数字抵消。

#3. 为什么弹栈条件不能写成 >=？

相等数字互换不会让高位变小，却会浪费删除次数。例如 "112"、k = 1，删除相等的第一个 "1" 会得到 "12"，而保留它并最终删除 "2" 可以得到更小的 "11"。

#4. 为什么一个数字可能触发多次弹栈？

删除原栈顶后，新栈顶仍可能大于当前数字。比如 "432" 中读到 "2" 且删除次数充足时，需要依次撤销之前保留的 "3"，甚至继续检查 "4"。

#5. 为什么扫描结束后要从末尾删除？

剩余删除次数说明此前没有足够的下降位置，当前保留序列非递减。删除末尾不会改变更高位前缀，而删除前面会让相同或更大的数字前移，所以末尾最优。

#6. 为什么清除前导零不算额外删除？

算法已经通过弹栈和末尾补删恰好移除了 k 个原始位置。清除前导零只是把同一个数值转换成题目要求的规范字符串表示。

#7. 嵌套循环为什么仍是 O(n)？

外层让每个数字入栈一次，内层每次执行都会永久弹出一个已经入栈的数字。入栈和出栈总次数都不超过 n，所以总操作数是线性的。

#8. 如果要求返回被删除的原始下标怎么办？

栈中改为保存 [digit, index]。弹栈和末尾补删时记录对应下标，最后将这些下标排序或按题目要求输出；贪心逻辑不变。

#常见错误

• 只说"维护递增栈"，没有解释高位优先的贪心依据。
• 只使用一次 if 弹栈，无法处理当前数字连续淘汰多个较大数字。
• 将条件写成 >=，错误删除相等数字。
• 扫描结束后忽略剩余删除次数。
• 从非递减结果的开头补删，而不是从末尾补删。
• 边扫描边跳过前导零，却没有正确区分格式化与删除次数。
• 删除所有数字后返回空字符串，而不是 "0"。
• 看到两层循环就误判为 O(n²)。

#可迁移总结

• 高位优先： 等长数字字符串的最小化，本质上是最小化字典序。
• 可撤销贪心： 新元素使旧选择不再最优时，用栈从最近选择开始撤销。
• 剩余操作： 单调结构中没有逆序可消除时，从影响最低的末尾处理。
• 一句话记忆： 当前数字更小时弹出左侧较大数字，删除次数有剩余时再删末尾，最后清理前导零。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 为什么在 "1432219" 中读到 "3" 时应该删除 "4"？