Leetcode 402. 移掉K位数字
贪心；单调栈
类型题：
解题思路：
核心：
从头到尾遍历，若当前字符cur小于前面的字符，则淘汰前面大的字符。因为若cur前面存在一个比cur还要大的字符，则构成的数字不会是最小。
实现：
维护一个单调栈，每次当前字符cur都跟栈顶K比较，若栈顶元素大于cur，则出栈，直到不满足栈顶元素>cur（这就是一个while循环）。 最终从栈底得到每一个字符，并构成答案。即对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到
- 栈为空
- 或者新的栈顶元素不大于当前数字
- 或者我们已经删除了k个数字
细节：
- 每删除一个栈顶元素，k要减1，若当前已经删除了k个了（k==0），不用比较了，cur直接进栈。即要满足k>0，才能从栈顶删除元素。
- 可能原字符串是升序的，例如123456，K=1，栈中元素为123456，很明显不能将栈中所有字符都返回，所以定义remain为最终留下的字符个数，即栈中一定有remain个字符。
- 可能会有前导0，在得到结果前要先删除前导0，从栈底删除，使用双端队列Deque方便操作。
class Solution {
public String removeKdigits(String num, int k) {
int length = num.length();
int remain = length - k;//保留remain个字符
Deque<Character> stack = new LinkedList<>();
for (int i = 0; i < length; ++i) {
char cur = num.charAt(i);
while (!stack.isEmpty() && stack.peekLast() > cur && k > 0) {
stack.pollLast();
k--;
}
stack.offerLast(cur);
}
while (stack.size() > remain) {
stack.pollLast();
}
while (!stack.isEmpty() && stack.peekFirst() == '0') {
stack.pollFirst();
}
StringBuilder ans = new StringBuilder();
for (char c : stack) {
ans.append(c);
}
return ans.length() == 0 ? "0" : ans.toString();
}
}
复杂度分析：
时间复杂度： O(n)。
空间复杂度： O(n)。栈存储数字的空间。
参考文章
https://leetcode-cn.com/problems/remove-k-digits/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-5/
https://leetcode-cn.com/problems/remove-k-digits/solution/yi-diao-kwei-shu-zi-by-leetcode-solution/