Article / 文章
LeetCode 第402题：移掉K位数字
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
📖 文章摘要
本文详细解析LeetCode第402题“移掉K位数字”，这是一道贪心算法和单调栈的经典问题。文章提供了完整的解题思路，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合想要学习贪心算法和单调栈的读者。
核心知识点： 贪心算法、单调栈、字符串处理
难度等级： 中等
推荐人群： 对贪心算法和单调栈感兴趣的进阶学习者
题目描述
给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
示例
示例 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。
提示
- 1 <= num.length <= 105
- num 仅由若干位数字（0-9）组成
- 除了 0 本身之外，num 不含任何前导零
解题思路
这道题可以使用贪心算法结合单调栈来解决。核心思路如下：
-
贪心策略
- 从左到右遍历数字
- 如果当前数字小于栈顶数字，且还可以删除数字（k>0）
- 则删除栈顶数字（贪心地让高位数字尽可能小）
-
单调栈维护
- 使用栈来维护当前保留的数字
- 保持栈中数字单调不降
- 最终栈中的数字就是结果
-
特殊情况处理
- 删除前导零
- 处理空串情况
- 处理k仍有剩余的情况
图解思路
算法步骤分析表
| 步骤 | 操作 | 状态 | 说明 |
|---|---|---|---|
| 初始状态 | - | 栈空 | 准备处理输入字符串 |
| 遍历字符 | 比较当前字符与栈顶 | 维护单调栈 | 如果当前字符更小且k>0，弹出栈顶 |
| 处理剩余k | 从末尾删除 | 完成删除操作 | 如果k仍大于0，从末尾删除k个字符 |
| 处理前导零 | 删除前导零 | 得到最终结果 | 确保结果不含前导零且非空 |
状态/情况分析表
| 情况 | 输入 | 输出 | 说明 |
|---|---|---|---|
| 基本情况 | “1432219”, k=3 | “1219” | 删除高位大数字 |
| 前导零 | “10200”, k=1 | “200” | 需要处理前导零 |
| 全部删除 | “10”, k=2 | “0” | 返回“0”而不是空串 |
代码实现
C# 实现
public class Solution {
public string RemoveKdigits(string num, int k) {
if (string.IsNullOrEmpty(num) || k >= num.Length)
return "0";
var stack = new Stack<char>();
// 遍历每个数字
foreach (char c in num) {
// 当前数字小于栈顶数字，且还可以删除数字时，删除栈顶
while (k > 0 && stack.Count > 0 && stack.Peek() > c) {
stack.Pop();
k--;
}
stack.Push(c);
}
// 如果k还没有用完，从末尾删除
while (k > 0 && stack.Count > 0) {
stack.Pop();
k--;
}
// 构建结果字符串，注意去除前导零
var result = new string(stack.Reverse().ToArray());
result = result.TrimStart('0');
return string.IsNullOrEmpty(result) ? "0" : result;
}
}Python 实现
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
if not num or k >= len(num):
return "0"
stack = []
# 遍历每个数字
for digit in num:
# 当前数字小于栈顶数字，且还可以删除数字时，删除栈顶
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# 如果k还没有用完，从末尾删除
while k > 0 and stack:
stack.pop()
k -= 1
# 构建结果字符串，去除前导零
result = ''.join(stack).lstrip('0')
return result if result else "0"C++ 实现
class Solution {
public:
string removeKdigits(string num, int k) {
if (num.empty() || k >= num.length())
return "0";
vector<char> stack;
// 遍历每个数字
for (char c : num) {
// 当前数字小于栈顶数字，且还可以删除数字时，删除栈顶
while (k > 0 && !stack.empty() && stack.back() > c) {
stack.pop_back();
k--;
}
stack.push_back(c);
}
// 如果k还没有用完，从末尾删除
while (k > 0 && !stack.empty()) {
stack.pop_back();
k--;
}
// 构建结果字符串
string result(stack.begin(), stack.end());
// 去除前导零
result.erase(0, result.find_first_not_of('0'));
return result.empty() ? "0" : result;
}
};执行结果
C# 实现
- 执行用时：84 ms
- 内存消耗：38.2 MB
Python 实现
- 执行用时：40 ms
- 内存消耗：15.8 MB
C++ 实现
- 执行用时：0 ms
- 内存消耗：7.1 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 84 ms | 38.2 MB | 代码简洁，但性能较差 |
| Python | 40 ms | 15.8 MB | 实现简单，性能中等 |
| C++ | 0 ms | 7.1 MB | 性能最优，内存占用最小 |
代码亮点
- 🎯 使用单调栈实现贪心策略
- 💡 高效处理字符串和前导零
- 🔍 优雅处理边界情况
- 🎨 代码结构清晰，易于理解和维护
常见错误分析
- 🚫 忘记处理前导零的情况
- 🚫 没有正确处理k值用完后的情况
- 🚫 栈操作顺序错误
- 🚫 返回空字符串而不是“0”
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 暴力法 | O(k×n) | O(n) | 思路简单 | 性能很差 |
| 贪心+单调栈 | O(n) | O(n) | 性能最优 | 需要理解单调栈 |
| 动态规划 | O(k×n) | O(k×n) | 通用性好 | 空间复杂度高 |
相关题目
- LeetCode 316. 去除重复字母 - 中等
- LeetCode 321. 拼接最大数 - 困难
- LeetCode 1081. 不同字符的最小子序列 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第402题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！