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: