1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public String removeKdigits(String num, int k) {
int[] nextSmaller = new int[num.length()];
Arrays.fill(nextSmaller, -1);
char[] numArray = num.toCharArray();
Deque<Integer> monoStack = new ArrayDeque<>();
for (int i = 0; i < numArray.length; i++) {
while (!monoStack.isEmpty() && numArray[i] < numArray[monoStack.peek()]) {
nextSmaller[monoStack.pop()] = i;
}
monoStack.push(i);
}
StringBuilder ans = new StringBuilder();
int ptr = 0;
while (ptr < nextSmaller.length) {
if (nextSmaller[ptr] != -1 && nextSmaller[ptr] - ptr <= k) {
k -= nextSmaller[ptr] - ptr;
ptr = nextSmaller[ptr];
} else {
if (ans.length() != 0 || numArray[ptr] != '0') {
ans.append(numArray[ptr]);
}
ptr += 1;
}
}
ans.setLength(Math.max(0, ans.length() - k));
return ans.length() == 0 ? "0" : ans.toString();
}
}
|
mono stack. 我们需要知道每一个digit它的next smaller是谁. 如果一个digit的next smaller距离自己的距离小于等于k, 那么我们可以把从自己到next smaller之前的数字都删掉, 同时也更新k的值. k就代表能删掉多少digits. 如果一个digit没有next smaller, 我们就暂时保留它. 等到最后, 如果k没用完, 那我们把最后的k个删掉(如果不足k个就都删掉). 这是因为留下来的都是没有next smaller的, 或者有但是距离太远的. 因此它们的位置已经是我们能够达到最小的位置了. 如果我们从前往后删除, 只会让数字更大. 因此我们从后面开始删除.
时间复杂度: O(n) 遍历两次num, n是num的长度.
空间复杂度: O(n) 用到了stack.
