企业官网建设流程全解析

移掉 K 位数字（LeetCode 402）贪心 + 栈解法全解析——algorithm-base 动画模拟系列

【免费下载链接】algorithm-base一位酷爱做饭的程序员，立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base

导读

本篇是 algorithm-base 开源仓库「栈和队列」模块中的经典中等难度题解，核心讲解如何用「贪心 + 栈」在只删除 K 位数字的前提下，使剩下的数字最小。读完本文你将掌握：为什么单调栈天然适配"移除高位较大数字"类问题、如何优雅处理前导零、以及遍历结束后 K 值仍有剩余时的收尾逻辑，并能够独立写出可直接通过判题的可运行 Java 代码。

题目描述

给定一个以字符串表示的非负整数num，移除这个数中的k位数字，使得剩下的数字最小。

注意：

• num的长度小于 10002 且 ≥ k。
• num不会包含任何前导零。

示例 1：

输入:num = "1432219", k = 3输出:"1219"解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2：

输入:num = "10200", k = 1输出:"200"解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3：

输入:num = "10", k = 2输出:"0"解释: 从原数字移除所有的数字，剩余为空就是 0。

题目本身很容易理解，三组示例几乎把所有特殊情况（高位删除、前导零、全部删除）都进行了举例，因此实现时思路清晰、边界完备。

核心思路：贪心 + 栈

为什么"删除高位大数字"更优

题目要求删除 K 位后剩余数字最小，数字的大小主要由高位决定：同样长度的数字，第一位最小的那个必然整体最小。因此贪心策略可以概括为——尽量在高位删除较大的数字。

具体来说：当遍历到当前位时，如果当前位小于前一位，那么删除前一位、保留当前位，会让高位的数字变小，从而让整体结果更小。这种"当前位 < 前一位"时删除前一位的操作，恰好是单调栈的经典弹出场景。

借助栈完成"能删则删"

栈具有先进后出的特性，非常适合保存"到目前为止保留下来"的数字序列，并支持在常数时间内查看（peek）和删除（pop）末尾元素。算法流程如下：

1. 从左到右遍历num的每一个字符；
2. 只要栈非空、k > 0且当前字符小于栈顶字符，就把栈顶弹出（相当于删掉前一位），同时k--；
3. 将当前字符入栈；
4. 遍历结束后，如果k仍大于 0，说明数字序列已经单调非递减、没有可删的"峰"，此时从栈顶（即数字尾部）再删除剩余次数的数字。

以num = "1432219", k = 3为例：遍历过程中，4 > 1保留、3 < 4删 4，2 < 3删 3，2与1之间2 > 1保留，1 < 2删 2……最终得到1219，恰好删除了高位的 4、3、2，剩下的数字最小。

再比如54321，删除 3 位得到21。由于整个序列单调递减，遍历过程中每一位都小于前一位，前 3 位被依次弹出，剩余的就是最小的21，这也印证了"当前位小于前一位则弹出前一位"这一贪心规则的可行性。

两个容易踩坑的关键细节

原题解的巧妙之处在于对两个边界问题的处理，这也是本题最容易写错的地方。

细节一：栈空时的0不直接入栈

如果栈为空且当前位是0，直接continue跳过本次循环（不改变 K 值）。

原因：如果0处于栈底，它前面没有比它更小的值，永远不会被弹出移除，只能留到最终输出前处理。而形如010的中间结果等价于10，首位的0最终必须去掉。与其最后再处理，不如一开始就不让它入栈——这样逻辑比官方题解更简洁，也少一类边界判断。注意这里的continue不会消耗 K 值，因为0本身不算"被删除的数字"，只是"不保留"。

细节二：遍历结束后 K 值可能仍有剩余

num = "1432219", k = 3的场景中，遍历过程中只删除了 2 位，但题目要求删除 3 位，剩余的数字（如尾部递增段）都是"当前位大于前一位"，不会再触发弹出。此时需要在遍历结束后，从栈顶（数字尾部）继续弹出，补足剩余的 K 次删除。

为什么从尾部删？因为经过第一阶段的弹出后，栈内已经是非递减序列（每一位都不小于前一位），此时删掉末尾（最大的数字）才能让结果最小。例如112，如果还有剩余删除次数，删掉尾部的2得到11，才是最优。

完整代码实现（Java）

class Solution { public String removeKdigits(String num, int k) { //特殊情况全部删除 if (num.length() == k) { return "0"; } char[] s = num.toCharArray(); Stack<Character> stack = new Stack<>(); //遍历数组 for (Character i : s) { //移除元素的情况，k-- while (!stack.isEmpty() && i < stack.peek() && k > 0) { stack.pop(); k--; } //栈为空，且当前位为0时，我们不需要将其入栈 if (stack.isEmpty() && i == '0') { continue; } stack.push(i); } while (k > 0) { stack.pop(); k--; } if (stack.isEmpty()) { return "0"; } //反转并返回字符串 StringBuilder str = new StringBuilder(); while (!stack.isEmpty()) { str.append(stack.pop()); } return str.reverse().toString(); } }

代码逐段解读

• 全删特判：num.length() == k时无论删哪几位结果都是空串，按题意返回"0"；
• 主循环：while (!stack.isEmpty() && i < stack.peek() && k > 0)是核心贪心动作——栈顶大于当前位且有删除额度时，弹出栈顶；注意i < stack.peek()是字符之间的比较，由于数字字符的字典序与数值序一致，直接比较即可；
• 前导零处理：stack.isEmpty() && i == '0'时continue，如细节一所述；
• 收尾补删：while (k > 0)从栈顶弹出补足剩余次数，对应细节二；
• 输出：栈底到栈顶才是数字的从左到右顺序，因此借助StringBuilder依次pop再reverse()得到最终字符串；若栈为空（如num="10", k=2），返回"0"。

复杂度分析

• 时间复杂度：O(n)。每个字符最多入栈一次、出栈一次，整体线性扫描（n 为num的长度）；
• 空间复杂度：O(n)。最坏情况下栈中保存接近全部字符。

栈操作基础回顾：本题用到的 API

本题是对栈基本功的一次完整演练，用到的 API 都能在仓库的 Leetcode常用类和函数.md 的「栈（Stack）」小节中找到对应说明：

其中"出栈后reverse()还原顺序"是字符串类栈题目的通用收尾套路，栈是先进后出，而数字的从左到右顺序恰好与栈底到栈顶一致，因此必须反转。若对栈的基本模型（LIFO、push/pop 语义）还不熟悉，可先阅读仓库前置知识文档 关于栈和队列的那些事.md，其中详细讲解了栈模型、栈的实现方式（Stack类与Deque接口）以及中缀/后缀表达式求值等应用场景。

同类题型对比：从"相邻重复"到"单调性"

「栈和队列」模块中与本例形成良好对照的是 leetcode1047 删除字符串中的所有相邻重复项.md：那道题是"相邻且相同"时弹出栈顶，本题是"当前位小于栈顶"时弹出栈顶。

两者都是"遍历 + 条件弹出 + 栈保留结果"的框架，区别只在弹出判定条件。更进一步，本题的弹出规则"新元素更小则弹出旧元素"正是单调递增栈的雏形，理解了 402 之后，可以继续阅读仓库「单调队列单调栈」模块的 leetcode739每日温度.md、接雨水.md 等题目，建立对单调栈应用场景的完整认知。

总结

LeetCode 402「移掉 K 位数字」虽然标注为中等难度，但它是理解"栈 + 贪心"组合拳的绝佳素材：贪心负责指明"删高位大数"的方向，栈负责在 O(n) 时间内高效执行删除与回退。全文围绕三个要点即可完全吃透：

1. 贪心规则：当前位小于前一位时，删除前一位更优；
2. 前导零：栈空时的0不入栈，简化收尾逻辑；
3. 尾部补删：遍历结束后 K 还有剩余，从栈顶（尾部）补删。

掌握了这三条，再遇到"删除 K 个元素使结果最大/最小"的变体题目（例如改为保留单调递减序列求最大数），只需调整弹出条件即可举一反三。

【免费下载链接】algorithm-base一位酷爱做饭的程序员，立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base