LeetCode 402中等单调栈 · 贪心
移掉 K 位数字 图解题解
这道题到底在问什么
给非负整数字符串 num，移除其中 K 位数字，使剩下的数字（按原顺序拼接）最小，返回这个最小数。
- 输入
- num="1432219", k=3
- 输出
- "1219"
最优解：一步一步想明白
- 3思路一句话：高位上谁大就先删谁，删够 K 个。用栈存答案，比栈顶小且有名额就弹栈，栈从底到顶不下降。下面一步步演给你看。
- 4上面是数字串 "1432219" 的每一位，下面这个栈用来存「保留下来的答案」，从底到顶始终保持不下降。一共可以删 3 位。
- 5轮到第 0 位数字 '1'。栈是空的，没有更大的高位要删，直接放进去。
- 6把 '1' 压入栈顶。此刻栈从底到顶是不下降的：1。这样高位永远不会出现「先大后小」的吃亏排列。
- 7轮到第 1 位 '4'，先看栈顶 '1'：'4' 不比栈顶 '1' 小，删它不会让数变小，保留栈顶，'4' 排到后面。
- 8把 '4' 压入栈顶。此刻栈从底到顶是不下降的：14。这样高位永远不会出现「先大后小」的吃亏排列。
- 9轮到第 2 位 '3'，先看栈顶 '4'：'3' 比 '4' 小，而且还有删除名额（k=3），那留着 '4' 在高位就吃亏——把它删掉。
- 10删掉 '4'：它在更高位上却比后面的 '3' 大，删了能让数变小。已用掉 1 个名额，还剩 k=2。继续看新栈顶要不要接着删。
- 11把 '3' 压入栈顶。此刻栈从底到顶是不下降的：13。这样高位永远不会出现「先大后小」的吃亏排列。
- 12轮到第 3 位 '2'，先看栈顶 '3'：'2' 比 '3' 小，而且还有删除名额（k=2），那留着 '3' 在高位就吃亏——把它删掉。
- 13删掉 '3'：它在更高位上却比后面的 '2' 大，删了能让数变小。已用掉 1 个名额，还剩 k=1。继续看新栈顶要不要接着删。
- 14把 '2' 压入栈顶。此刻栈从底到顶是不下降的：12。这样高位永远不会出现「先大后小」的吃亏排列。
- 15轮到第 4 位 '2'，先看栈顶 '2'：'2' 不比栈顶 '2' 小，删它不会让数变小，保留栈顶，'2' 排到后面。
- 16把 '2' 压入栈顶。此刻栈从底到顶是不下降的：122。这样高位永远不会出现「先大后小」的吃亏排列。
- 17轮到第 5 位 '1'，先看栈顶 '2'：'1' 比 '2' 小，而且还有删除名额（k=1），那留着 '2' 在高位就吃亏——把它删掉。
- 18删掉 '2'：它在更高位上却比后面的 '1' 大，删了能让数变小。已用掉 1 个名额，还剩 k=0。继续看新栈顶要不要接着删。
- 19把 '1' 压入栈顶。此刻栈从底到顶是不下降的：121。这样高位永远不会出现「先大后小」的吃亏排列。
- 20轮到第 6 位 '9'，先看栈顶 '1'：'9' 不比栈顶 '1' 小，删它不会让数变小，保留栈顶，'9' 排到后面。
- 21把 '9' 压入栈顶。此刻栈从底到顶是不下降的：1219。这样高位永远不会出现「先大后小」的吃亏排列。
- 22别忘了最后一步：检查开头有没有前导 0（像 "0200" 要写成 "200"）。这里开头是 '1'，不是 0，直接就是答案。
- 23一共删掉 3 位，剩下从底到顶就是答案 "1219"。整个过程只入栈、出栈各一次，O(n)。
⚠️ 容易写错的地方
✗ 错：用 ≥ 弹栈
✓ 对：严格 > 才弹（栈顶比当前大才删）
相等不必删，留着名额删后面更大的更划算
✗ 错：扫完忘了 k 还有剩
✓ 对：从尾部再删 k 个
如 "12345" k=2，全程不触发弹栈，得删末尾的 "45"
✗ 错：忘记去前导 0
✓ 对：结果开头连续的 0 要去掉
"10200" 删 1 位得 "0200"，要写成 "200"
完整代码（Python / C++ / Java）
Python
def removeKdigits(num, k):
stack = []
for d in num:
while k and stack and stack[-1] > d:
stack.pop() # 删更大的高位
k -= 1
stack.append(d)
stack = stack[:len(stack)-k] # k 有剩删尾部
return "".join(stack).lstrip("0") or "0"C++
string removeKdigits(string num, int k){
string st;
for(char d : num){
while(k && !st.empty() && st.back() > d){
st.pop_back(); k--;
}
st.push_back(d);
}
st.resize(st.size() - k); // k 有剩删尾
int p = 0;
while(p < (int)st.size() && st[p]=='0') p++;
st = st.substr(p);
return st.empty() ? "0" : st;
}Java
public String removeKdigits(String num, int k) {
Deque<Character> st = new ArrayDeque<>();
for (char d : num.toCharArray()) {
while (k > 0 && !st.isEmpty() && st.peekLast() > d) {
st.pollLast(); k--; // 删更大的高位
}
st.offerLast(d);
}
while (k-- > 0) st.pollLast(); // k 有剩删尾
StringBuilder sb = new StringBuilder();
for (char c : st) sb.append(c);
int p = 0;
while (p < sb.length() && sb.charAt(p) == '0') p++;
String res = sb.substring(p);
return res.isEmpty() ? "0" : res;
}复杂度
时间
O(n)
每位数字进出栈各一次
空间
O(n)
栈最坏保留所有数字
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 移掉 K 位数字 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么是「单调不降」的栈，而不是不升？+
数字越靠前权重越大，要让高位尽量小，所以保留的序列应当不下降；一旦后面来个更小的，就把前面更大的高位删掉。
为什么 k 有剩要从尾部删？+
没触发弹栈说明栈已经单调不降，越靠后的数字越大，此时删末尾的大数字才能让整体最小。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 移掉 K 位数字 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。