LeetCode 402 - 移掉 K 位数字

文章目录

• • 摘要
  • 描述
  • 题解答案
  • 题解代码分析
  • • 代码逻辑逐步拆解：
  • 示例测试及结果
  • 时间复杂度
  • 空间复杂度
  • 总结

摘要

在很多前端或后端的业务逻辑中，我们经常要处理数字的“裁剪”问题，比如在账单明细里自动保留最小金额组合、或在数据压缩时尽量保留较小值。LeetCode 第 402 题《移掉 K 位数字》（Remove K Digits）就是一个非常贴近这种逻辑的算法题。

题目的核心是：给定一个非负整数（以字符串形式表示），从中移除 k 个数字，使得剩下的数字最小化。
看似简单，但要保证最小值且保持相对顺序，就必须巧妙地使用单调栈（Monotonic Stack）。

描述

题目要求如下：

给你一个以字符串表示的非负整数 num 和一个整数 k，移除这个数中的 k 位数字，使得剩下的数字最小。返回结果仍然以字符串形式表示。

例如：

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

解释：
我们删掉 4、3、2，得到 1219，这是最小的组合。

再看另一个例子：

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

因为去掉开头的 1 后，最小结果是 “200”，同时要注意不能有前导零。

最后一种极端情况：

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

删光了，只能输出 “0”。

题解答案

思路其实很自然：

1. 我们想要一个尽可能小的数字。
2. 所以，每当我们看到一个“比前一个更小”的数字，就说明前面的数字没必要留着，可以删掉让整体更小。
3. 这正是典型的 “单调递增栈” 思想。
   我们用一个栈来存放数字，如果当前数字比栈顶小，就把栈顶弹出（删掉）直到不满足条件或删够了 k 个。
4. 最后，如果还没删够，就从尾部继续删。
5. 结果去掉前导零，若为空返回 “0”。

题解代码分析

下面是完整的 Swift 实现，可以直接在 Xcode 或 Playground 中运行：

1import Foundation
2
3class Solution {
4    func removeKdigits(_ num: String, _ k: Int) -> String {
5        var stack: [Character] = []
6        var removeCount = k
7
8        for digit in num {
9            // 每当当前数字比栈顶小，就弹出栈顶（相当于删除）
10            while removeCount > 0, let last = stack.last, last > digit {
11                stack.removeLast()
12                removeCount -= 1
13            }
14            stack.append(digit)
15        }
16
17        // 如果还没删够，就从尾部删除
18        while removeCount > 0, !stack.isEmpty {
19            stack.removeLast()
20            removeCount -= 1
21        }
22
23        // 构建最终字符串并去掉前导零
24        var result = String(stack).drop(while: { $0 == "0" })
25        return result.isEmpty ? "0" : String(result)
26    }
27}
28
29// MARK: - 可运行示例
30let solution = Solution()
31print(solution.removeKdigits("1432219", 3)) // 输出: 1219
32print(solution.removeKdigits("10200", 1))   // 输出: 200
33print(solution.removeKdigits("10", 2))      // 输出: 0
34

代码逻辑逐步拆解：

• 栈的核心思想
  栈用来保存当前有效的数字序列。每个新数字进来之前，都会看一眼栈顶是否“更大”，如果更大，就弹出。
  比如处理 "1432219"：
  • 1 → [1]
  • 4 → [1, 4]
  • 3 → 3 < 4 → 弹出 4 → [1, 3]
  • 2 → 2 < 3 → 弹出 3 → [1, 2]
  • 2 → [1, 2, 2]
  • 1 → 1 < 2 → 弹出两个 2 → [1, 1]
  • 9 → [1, 1, 9]
    最终得到 1219。
• 删除次数控制
  我们用 removeCount 计数，每次弹出一个数字就减 1。
  如果循环结束后还没删够，就直接从尾巴删，保持最小化。
• 前导零处理
  比如 “10200” → 删除 1 后变成 “0200”，要去掉前导零，得到 “200”。

示例测试及结果

我们来跑几组不同的示例看看结果是否符合预期。

1let solution = Solution()
2print(solution.removeKdigits("1432219", 3)) // 1219
3print(solution.removeKdigits("10200", 1))   // 200
4print(solution.removeKdigits("10", 2))      // 0
5print(solution.removeKdigits("1234567890", 9)) // 0
6print(solution.removeKdigits("112", 1))     // 11
7

输出结果如下：

11219
2200
30
40
511
6

非常符合预期。

时间复杂度

• 主循环中每个数字最多入栈、出栈一次，
  所以整体复杂度是 O(n)，其中 n 是字符串长度。

这种复杂度对于 num.length 高达 10^5 的情况也能轻松应对。

空间复杂度

• 我们用了一个栈来存储数字，最坏情况下保存所有字符，
  所以空间复杂度是 O(n)。

总结

这道题看似是个字符串问题，其实本质是个“贪心 + 单调栈”的组合问题。

• 贪心保证我们每一步都尽可能让左边数字小；
• 栈保证我们能方便地删除不合适的数字；
• 去除前导零的细节让结果符合格式要求。

在实际开发中，这种思想也很常见，比如：

• 表单验证时自动修剪冗余字符
• 财务系统中压缩冗余金额字段
• UI 中动态展示最小数值状态

这道题不仅是算法题，更像是“如何在一堆数里精简出最优解”的典型案例。

《LeetCode 402 - 移掉 K 位数字》 是转载文章，点击查看原文。