题目
概述：给定一个自然数字符串，要求从中移掉K个数，使得剩下的字符所组成的自然数最小
-
输入：自然数字符串，长度范围[k, 10002]
输入自然数字符串不包含前导零
-
输出：剩下的字符所组成的自然数字符串
输出不能包含前导零
若最后没有剩下任何字符，则返回“0”
思路
由于需要暂存之前的数字跟后面的数字比较判断是否移掉该数字，所以考虑用栈实现
如果自然数字符串的长度等于k，则返回“0”
-
遍历剩余字符串直至剩余字符串为空或移掉的字符个数等于k：
- 栈为空 => 当前数字入栈
- 当前数字 >= 栈顶数字 => 当前数字入栈
- 当前数字 < 栈顶数字 => 栈顶数字出栈，移掉字符个数+1，循环
若移掉的字符个数 < k => 将栈出栈（k - 移掉的字符个数）次
将栈中元素逆序与剩余字符串拼接，消去前导0，若最后为空串则返回“0”，否则直接返回
代码
class Solution {
public String removeKdigits(String num, int k) {
if (num.length() == k) {
return "0";
}
LinkedList<Character> stack = new LinkedList<>();
int i = 0;
while (i < num.length() && k > 0) {
if (stack.isEmpty() || stack.peek() - num.charAt(i) <= 0) {
stack.push(num.charAt(i++));
} else {
stack.pop();
--k;
}
}
while (k > 0) {
stack.pop();
--k;
}
StringBuilder sb = new StringBuilder(num.substring(i));
while (!stack.isEmpty()) {
sb.insert(0, stack.pop());
}
String result = sb.toString();
int s = 0;
while (s < result.length() && '0' == result.charAt(s)) {
++s;
}
if (s == result.length()) {
return "0";
} else {
return result.substring(s);
}
}
}
