402. 移掉 K 位数字
题目描述
输入一个用字符串表示的非负整数 num 和一个整数 k。num 除了本身是 "0" 的情况外，没有前导零。
从 num 中删掉恰好 k 个数字，剩下的数字保持原有次序，组成一个新数。让这个新数尽可能小。
以字符串返回这个最小值。结果要去掉前导零；如果删完后什么都不剩或只剩零，返回 "0"。
示例 1
输入：num = "1432219", k = 3 输出："1219"
解释：删掉 4、3、2，得到 1219。
示例 2
输入：num = "10200", k = 1 输出："200"
解释：删掉开头的 1 后剩 "0200"，去掉前导零为 "200"。
示例 3
输入：num = "10", k = 2 输出："0"
解释：两个数字都被删掉，结果为 "0"。
数据范围
1 <= k <= num.length <= 10^5num只由数字0-9组成- 除
0本身外，num没有前导零
解题思路
数字越靠左，权重越大，所以要让高位尽量小。从左到右扫描，维护一个单调不减的栈：遇到更小的数字 d 时，只要还能删（k>0）且栈顶比 d 大，就弹出栈顶——把较大的高位换成更小的 d 一定更优。扫描完若 k 还有剩余，栈已单调不减，删掉末尾 k 位最划算。最后去掉前导零。
为什么正确
栈内数字从底到顶单调不减；栈就是在已扫描前缀上、用掉 (原 k − 当前 k) 次删除后能得到的最小前缀。
复杂度分析
时间 O(n)（每个数字最多入栈、出栈各一次），空间 O(n)。
易错点
两个容易漏的收尾：扫描完 k 可能还没用完（例如 "12345"），要删末尾；结果可能有前导零或为空（例如 "10", k=2），要去零并在空时返回 "0"。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
stack = []
for d in num:
while k and stack and stack[-1] > d:
stack.pop()
k -= 1
stack.append(d)
if k:
stack = stack[:-k]
return ''.join(stack).lstrip('0') or '0'class Solution {
public String removeKdigits(String num, int k) {
StringBuilder stack = new StringBuilder();
for (char d : num.toCharArray()) {
while (k > 0 && stack.length() > 0 && stack.charAt(stack.length() - 1) > d) {
stack.deleteCharAt(stack.length() - 1);
k--;
}
stack.append(d);
}
if (k > 0) {
stack.setLength(stack.length() - k);
}
int p = 0;
while (p < stack.length() && stack.charAt(p) == '0') p++;
String res = stack.substring(p);
return res.isEmpty() ? "0" : res;
}
}class Solution {
public:
string removeKdigits(string num, int k) {
string stack;
for (char d : num) {
while (k && !stack.empty() && stack.back() > d) {
stack.pop_back();
k--;
}
stack.push_back(d);
}
if (k) {
stack.resize(stack.size() - k);
}
int p = 0;
while (p < (int)stack.size() && stack[p] == '0') p++;
string res = stack.substr(p);
return res.empty() ? "0" : res;
}
};func removeKdigits(num string, k int) string {
stack := []byte{}
for i := 0; i < len(num); i++ {
d := num[i]
for k > 0 && len(stack) > 0 && stack[len(stack)-1] > d {
stack = stack[:len(stack)-1]
k--
}
stack = append(stack, d)
}
if k > 0 {
stack = stack[:len(stack)-k]
}
p := 0
for p < len(stack) && stack[p] == '0' {
p++
}
if p == len(stack) {
return "0"
}
return string(stack[p:])
}var removeKdigits = function(num, k) {
let stack = [];
for (const d of num) {
while (k && stack.length && stack[stack.length - 1] > d) {
stack.pop();
k--;
}
stack.push(d);
}
if (k) {
stack = stack.slice(0, stack.length - k);
}
return stack.join('').replace(/^0+/, '') || '0';
};function removeKdigits(num: string, k: number): string {
let stack: string[] = [];
for (const d of num) {
while (k && stack.length && stack[stack.length - 1] > d) {
stack.pop();
k--;
}
stack.push(d);
}
if (k) {
stack = stack.slice(0, stack.length - k);
}
return stack.join('').replace(/^0+/, '') || '0';
}