402 Remove K Digits

1. Question

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
Input: num = "1432219", k = 3
2
Output: "1219"
3
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Copied!
Example 2:
1
Input: num = "10200", k = 1
2
Output: "200"
3
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Copied!
Example 3:
1
Input: num = "10", k = 2
2
Output: "0"
3
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
Copied!

2. Implementation

思路:这题思路和Remove Duplicate Letters一样,利用单调栈保持输出结果的单调性,只是要注意一些Corner cases
1
class Solution {
2
public String removeKdigits(String num, int k) {
3
int len = num.length();
4
5
if (k == len) {
6
return "0";
7
}
8
9
Stack<Character> stack = new Stack<>();
10
11
for (char digit : num.toCharArray()) {
12
while (k > 0 && !stack.isEmpty() && stack.peek() > digit) {
13
stack.pop();
14
--k;
15
}
16
17
stack.push(digit);
18
}
19
20
while (k > 0) {
21
stack.pop();
22
--k;
23
}
24
25
StringBuilder res = new StringBuilder();
26
while (!stack.isEmpty()) {
27
res.append(stack.pop());
28
}
29
30
while (res.length() > 1 && res.charAt(res.length() - 1) == '0') {
31
res.deleteCharAt(res.length() - 1);
32
}
33
return res.reverse().toString();
34
}
35
}
Copied!

3. Time & Space Complexity

时间和空间复杂度都是O(n)