LeetCode 402: Remove K Digits (Monotonic Stack Greedy)
LeetCode 402GreedyMonotonic StackToday we solve LeetCode 402 - Remove K Digits.
Source: https://leetcode.com/problems/remove-k-digits/
English
Problem Summary
Given a non-negative integer string num and integer k, remove exactly k digits so the remaining number is the smallest possible.
Key Insight
To minimize lexicographically (and numerically), when a new digit is smaller than previous kept digits, we should remove those larger previous digits first. This is exactly a monotonic non-decreasing stack strategy.
Algorithm
- Iterate digits in num.
- While k > 0 and stack top is larger than current digit, pop stack and decrement k.
- Push current digit.
- If k > 0 after scan, remove last k digits (largest suffix impact).
- Strip leading zeros; return "0" if empty.
Complexity Analysis
Let n be length of num.
Time: O(n) (each digit pushed/popped at most once).
Space: O(n).
Common Pitfalls
- Forgetting the post-processing pops when digits are already increasing.
- Not removing leading zeros.
- Returning empty string instead of "0".
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String removeKdigits(String num, int k) {
StringBuilder st = new StringBuilder();
for (char c : num.toCharArray()) {
while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > c) {
st.deleteCharAt(st.length() - 1);
k--;
}
st.append(c);
}
while (k > 0 && st.length() > 0) {
st.deleteCharAt(st.length() - 1);
k--;
}
int i = 0;
while (i < st.length() && st.charAt(i) == '0') i++;
String ans = st.substring(i);
return ans.isEmpty() ? "0" : ans;
}
}func removeKdigits(num string, k int) string {
st := make([]byte, 0, len(num))
for i := 0; i < len(num); i++ {
c := num[i]
for k > 0 && len(st) > 0 && st[len(st)-1] > c {
st = st[:len(st)-1]
k--
}
st = append(st, c)
}
for k > 0 && len(st) > 0 {
st = st[:len(st)-1]
k--
}
i := 0
for i < len(st) && st[i] == '0' {
i++
}
if i == len(st) {
return "0"
}
return string(st[i:])
}class Solution {
public:
string removeKdigits(string num, int k) {
string st;
for (char c : num) {
while (k > 0 && !st.empty() && st.back() > c) {
st.pop_back();
k--;
}
st.push_back(c);
}
while (k > 0 && !st.empty()) {
st.pop_back();
k--;
}
int i = 0;
while (i < (int)st.size() && st[i] == '0') i++;
string ans = st.substr(i);
return ans.empty() ? "0" : ans;
}
};class Solution:
def removeKdigits(self, num: str, k: int) -> str:
st = []
for c in num:
while k > 0 and st and st[-1] > c:
st.pop()
k -= 1
st.append(c)
while k > 0 and st:
st.pop()
k -= 1
ans = ''.join(st).lstrip('0')
return ans if ans else "0"var removeKdigits = function(num, k) {
const st = [];
for (const c of num) {
while (k > 0 && st.length > 0 && st[st.length - 1] > c) {
st.pop();
k--;
}
st.push(c);
}
while (k > 0 && st.length > 0) {
st.pop();
k--;
}
const ans = st.join('').replace(/^0+/, '');
return ans.length ? ans : '0';
};中文
题目概述
给定非负整数字符串 num 和整数 k，删除恰好 k 位数字，使剩下的数字最小。
核心思路
想让结果最小，应该优先把前面较大的数字删掉，让更小的数字尽量靠前。遇到新数字更小时，不断弹出前面比它大的数字，这就是单调不降栈贪心。
算法步骤
- 逐位遍历 num。
- 当 k > 0 且栈顶大于当前位时，持续弹栈并 k--。
- 当前位入栈。
- 遍历结束若 k 仍大于 0，继续从末尾删除 k 位。
- 去掉前导零；若为空返回 "0"。
复杂度分析
设 num 长度为 n。
时间复杂度：O(n)。
空间复杂度：O(n)。
常见陷阱
- 忽略“最终还要补删”的步骤（例如输入单调递增时）。
- 忘记去掉前导零。
- 结果为空时返回空串而不是 "0"。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String removeKdigits(String num, int k) {
StringBuilder st = new StringBuilder();
for (char c : num.toCharArray()) {
while (k > 0 && st.length() > 0 && st.charAt(st.length() - 1) > c) {
st.deleteCharAt(st.length() - 1);
k--;
}
st.append(c);
}
while (k > 0 && st.length() > 0) {
st.deleteCharAt(st.length() - 1);
k--;
}
int i = 0;
while (i < st.length() && st.charAt(i) == '0') i++;
String ans = st.substring(i);
return ans.isEmpty() ? "0" : ans;
}
}func removeKdigits(num string, k int) string {
st := make([]byte, 0, len(num))
for i := 0; i < len(num); i++ {
c := num[i]
for k > 0 && len(st) > 0 && st[len(st)-1] > c {
st = st[:len(st)-1]
k--
}
st = append(st, c)
}
for k > 0 && len(st) > 0 {
st = st[:len(st)-1]
k--
}
i := 0
for i < len(st) && st[i] == '0' {
i++
}
if i == len(st) {
return "0"
}
return string(st[i:])
}class Solution {
public:
string removeKdigits(string num, int k) {
string st;
for (char c : num) {
while (k > 0 && !st.empty() && st.back() > c) {
st.pop_back();
k--;
}
st.push_back(c);
}
while (k > 0 && !st.empty()) {
st.pop_back();
k--;
}
int i = 0;
while (i < (int)st.size() && st[i] == '0') i++;
string ans = st.substr(i);
return ans.empty() ? "0" : ans;
}
};class Solution:
def removeKdigits(self, num: str, k: int) -> str:
st = []
for c in num:
while k > 0 and st and st[-1] > c:
st.pop()
k -= 1
st.append(c)
while k > 0 and st:
st.pop()
k -= 1
ans = ''.join(st).lstrip('0')
return ans if ans else "0"var removeKdigits = function(num, k) {
const st = [];
for (const c of num) {
while (k > 0 && st.length > 0 && st[st.length - 1] > c) {
st.pop();
k--;
}
st.push(c);
}
while (k > 0 && st.length > 0) {
st.pop();
k--;
}
const ans = st.join('').replace(/^0+/, '');
return ans.length ? ans : '0';
};
Comments