Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.

Example 1:

1
2
3
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

1
2
3
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

1
2
3
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.


最直接的想法就是,如果两个数字left, right相邻,当left > right时,删除left,可以保证所得的数最小。实际上就是从左向右边找peak, 每次删除掉peak。
可以用Stack来存储每个字符, 每次push的时候检查栈顶元素是不是比当前的大,如果是,pop栈顶元素, 如果不是,push当前元素。当然最多也只能pop k次, 因为只能删除k个字符。
因为输出的时候要从栈底开始,所以Deque才能满足需求。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public String removeKdigits(String num, int k) {
Deque<Character> deque = new ArrayDeque<>();
int count = 0;
for (int i = 0; i < num.length(); i++) {
char c = num.charAt(i);
while (!deque.isEmpty() && deque.peek() > c && count < k) {
count++;
deque.pop();
}
deque.push(c);
}
while (!deque.isEmpty() && deque.peekLast() == '0') {
deque.pollLast();
k++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < num.length() - k; i++) {
sb.append(deque.pollLast());
}
return sb.length() == 0 ? "0" : sb.toString();
}

也有人用Array直接模拟了Deque的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String removeKdigits3(String num, int k) {
int digits = num.length() - k;
char[] stk = new char[num.length()];
int top = 0;
// k keeps track of how many characters we can remove
// if the previous character in stk is larger than the current one
// then removing it will get a smaller number
// but we can only do so when k is larger than 0
for (int i = 0; i < num.length(); ++i) {
char c = num.charAt(i);
while (top > 0 && stk[top - 1] > c && k > 0) {
top -= 1;
k -= 1;
}
stk[top++] = c;
}
// find the index of first non-zero digit
int idx = 0;
while (idx < digits && stk[idx] == '0') idx++;
return idx == digits ? "0" : new String(stk, idx, digits - idx);
}

Ref: