移掉 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末尾元素。算法流程如下从左到右遍历num的每一个字符只要栈非空、k 0且当前字符小于栈顶字符就把栈顶弹出相当于删掉前一位同时k--将当前字符入栈遍历结束后如果k仍大于 0说明数字序列已经单调非递减、没有可删的峰此时从栈顶即数字尾部再删除剩余次数的数字。以num 1432219, k 3为例遍历过程中4 1保留、3 4删 42 3删 32与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才是最优。完整代码实现Javaclass Solution { public String removeKdigits(String num, int k) { //特殊情况全部删除 if (num.length() k) { return 0; } char[] s num.toCharArray(); StackCharacter 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()得到最终字符串若栈为空如num10, k2返回0。复杂度分析时间复杂度O(n)。每个字符最多入栈一次、出栈一次整体线性扫描n 为num的长度空间复杂度O(n)。最坏情况下栈中保存接近全部字符。栈操作基础回顾本题用到的 API本题是对栈基本功的一次完整演练用到的 API 都能在仓库的 Leetcode常用类和函数.md 的「栈Stack」小节中找到对应说明API作用本题中的使用位置new StackCharacter()创建栈初始化结果容器push(e)元素入栈保留当前数字peek()查看栈顶但不移除与当前字符比较大小pop()弹出栈顶并返回执行删除操作isEmpty()判断栈是否为空循环条件与前导零判断StringBuilder.append(pop())reverse()逆序出栈后反转得到正序字符串最终结果组装其中出栈后reverse()还原顺序是字符串类栈题目的通用收尾套路栈是先进后出而数字的从左到右顺序恰好与栈底到栈顶一致因此必须反转。若对栈的基本模型LIFO、push/pop 语义还不熟悉可先阅读仓库前置知识文档 关于栈和队列的那些事.md其中详细讲解了栈模型、栈的实现方式Stack类与Deque接口以及中缀/后缀表达式求值等应用场景。同类题型对比从相邻重复到单调性「栈和队列」模块中与本例形成良好对照的是 leetcode1047 删除字符串中的所有相邻重复项.md那道题是相邻且相同时弹出栈顶本题是当前位小于栈顶时弹出栈顶。题目弹出条件贪心方向1047 删除相邻重复项当前字符 栈顶消除相邻重复402 移掉 K 位数字当前字符 栈顶高位取小两者都是遍历 条件弹出 栈保留结果的框架区别只在弹出判定条件。更进一步本题的弹出规则新元素更小则弹出旧元素正是单调递增栈的雏形理解了 402 之后可以继续阅读仓库「单调队列单调栈」模块的 leetcode739每日温度.md、接雨水.md 等题目建立对单调栈应用场景的完整认知。总结LeetCode 402「移掉 K 位数字」虽然标注为中等难度但它是理解栈 贪心组合拳的绝佳素材贪心负责指明删高位大数的方向栈负责在 O(n) 时间内高效执行删除与回退。全文围绕三个要点即可完全吃透贪心规则当前位小于前一位时删除前一位更优前导零栈空时的0不入栈简化收尾逻辑尾部补删遍历结束后 K 还有剩余从栈顶尾部补删。掌握了这三条再遇到删除 K 个元素使结果最大/最小的变体题目例如改为保留单调递减序列求最大数只需调整弹出条件即可举一反三。【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 移掉 K 位数字（LeetCode 402）贪心 + 栈解法全解析——algorithm-base 动画模拟系列
移掉 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末尾元素。算法流程如下从左到右遍历num的每一个字符只要栈非空、k 0且当前字符小于栈顶字符就把栈顶弹出相当于删掉前一位同时k--将当前字符入栈遍历结束后如果k仍大于 0说明数字序列已经单调非递减、没有可删的峰此时从栈顶即数字尾部再删除剩余次数的数字。以num 1432219, k 3为例遍历过程中4 1保留、3 4删 42 3删 32与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才是最优。完整代码实现Javaclass Solution { public String removeKdigits(String num, int k) { //特殊情况全部删除 if (num.length() k) { return 0; } char[] s num.toCharArray(); StackCharacter 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()得到最终字符串若栈为空如num10, k2返回0。复杂度分析时间复杂度O(n)。每个字符最多入栈一次、出栈一次整体线性扫描n 为num的长度空间复杂度O(n)。最坏情况下栈中保存接近全部字符。栈操作基础回顾本题用到的 API本题是对栈基本功的一次完整演练用到的 API 都能在仓库的 Leetcode常用类和函数.md 的「栈Stack」小节中找到对应说明API作用本题中的使用位置new StackCharacter()创建栈初始化结果容器push(e)元素入栈保留当前数字peek()查看栈顶但不移除与当前字符比较大小pop()弹出栈顶并返回执行删除操作isEmpty()判断栈是否为空循环条件与前导零判断StringBuilder.append(pop())reverse()逆序出栈后反转得到正序字符串最终结果组装其中出栈后reverse()还原顺序是字符串类栈题目的通用收尾套路栈是先进后出而数字的从左到右顺序恰好与栈底到栈顶一致因此必须反转。若对栈的基本模型LIFO、push/pop 语义还不熟悉可先阅读仓库前置知识文档 关于栈和队列的那些事.md其中详细讲解了栈模型、栈的实现方式Stack类与Deque接口以及中缀/后缀表达式求值等应用场景。同类题型对比从相邻重复到单调性「栈和队列」模块中与本例形成良好对照的是 leetcode1047 删除字符串中的所有相邻重复项.md那道题是相邻且相同时弹出栈顶本题是当前位小于栈顶时弹出栈顶。题目弹出条件贪心方向1047 删除相邻重复项当前字符 栈顶消除相邻重复402 移掉 K 位数字当前字符 栈顶高位取小两者都是遍历 条件弹出 栈保留结果的框架区别只在弹出判定条件。更进一步本题的弹出规则新元素更小则弹出旧元素正是单调递增栈的雏形理解了 402 之后可以继续阅读仓库「单调队列单调栈」模块的 leetcode739每日温度.md、接雨水.md 等题目建立对单调栈应用场景的完整认知。总结LeetCode 402「移掉 K 位数字」虽然标注为中等难度但它是理解栈 贪心组合拳的绝佳素材贪心负责指明删高位大数的方向栈负责在 O(n) 时间内高效执行删除与回退。全文围绕三个要点即可完全吃透贪心规则当前位小于前一位时删除前一位更优前导零栈空时的0不入栈简化收尾逻辑尾部补删遍历结束后 K 还有剩余从栈顶尾部补删。掌握了这三条再遇到删除 K 个元素使结果最大/最小的变体题目例如改为保留单调递减序列求最大数只需调整弹出条件即可举一反三。【免费下载链接】algorithm-base一位酷爱做饭的程序员立志用动画将算法说的通俗易懂。我的面试网站 www.chengxuchu.com项目地址: https://gitcode.com/gh_mirrors/al/algorithm-base创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考