给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k 位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 java单调栈
时间: 2024-03-15 15:46:30 浏览: 84
输入n个整数,输出其中最小的k个
好的,这个问题需要用到单调栈来解决。我们可以从高位到低位遍历整个字符串,每次遍历时,如果当前数字比栈顶数字小,则将栈顶数字出栈,直到栈为空或者栈顶数字比当前数字小,然后将当前数字入栈。这样可以保证栈顶元素是当前最小的数字。如果已经移除了 k 个数字,但是还有剩余数字未处理,则将剩余数字全部入栈。如果栈中元素个数大于 num.length() - k,则将多余的元素出栈,最后将栈中元素组合成字符串即可。
以下是Java代码实现:
```java
public String removeKdigits(String num, int k) {
if (num.length() == k) {
return "0";
}
Stack<Character> stack = new Stack<>();
int i = 0;
while (i < num.length()) {
while (k > 0 && !stack.isEmpty() && stack.peek() > num.charAt(i)) {
stack.pop();
k--;
}
stack.push(num.charAt(i));
i++;
}
while (k > 0) {
stack.pop();
k--;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
sb.reverse();
while (sb.length() > 1 && sb.charAt(0) == '0') {
sb.deleteCharAt(0);
}
return sb.toString();
}
```
希望能帮到你!
阅读全文