移掉 K 位数字
题目链接
移掉 K 位数字
题目描述
注意点
- 1 <= k <= num.length <= 10^5
- num 仅由若干位数字（0 - 9）组成
- 除了 0 本身之外，num 不含任何前导零
解答思路
- 关键是怎样移掉K位数字保证移除后的数字是最小的。观察规律可得，为了保证数字更小，需要保证高位的数字更小，也就是需要保证num从高到低是递增的
- 可以使用栈存储高位的数字，栈顶的数字最大，对于任意一个位置的数字，如果其比栈顶的数字更小，且此时K > 0（能够移除数字），则将栈中所有比当前数字小的数字都出栈，直到总共移除了K个数字或栈中数字都递增为止
代码
class Solution {public String removeKdigits(String num, int k) {Deque<Character> dq = new ArrayDeque<>();int n = num.length();for (int i = 0; i < n; i++) {char c = num.charAt(i);while (k > 0 && !dq.isEmpty() && c < dq.peek()) {dq.pop();k--;}dq.push(c);}// 栈中元素全部递增，但是还要继续移除数字while (k > 0) {dq.pop();k--;}StringBuilder sb = new StringBuilder();while (!dq.isEmpty()) {char c = dq.pollLast();if (sb.length() != 0 || c != '0') {sb.append(c);}}if (sb.length() == 0) {return "0";}return sb.toString();}
}
关键点
- 找到移掉K位数字后保证数字最小的规律
- 移掉K位数字后如果String为空则返回0
- 如果栈中元素都递增后仍然没有移除K位数字，则还需要继续移除末尾的数字，直到移除了K位数字为止