给定一个以字符串表示的非负整数 num*，移除这个数中的 *k 位数字，使得剩下的数字最小。
注意:
- num 的长度小于 10002 且 ≥ k。
- num 不会包含任何前导零。
示例 1 :
1
2
3
| 输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
|
示例 2 :
1
2
3
| 输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
|
示例 3 :
1
2
3
| 输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
|
方法一：贪心+单调栈
对于两个长度相同的序列，最左边的不同数字决定了这两个数字的大小。例如，对于 A = laxxx，B = lbxxx，如果 a > b 则 A > B。
要使剩下的数字最小，需要保证靠前的数字尽可能小。以 425 为例，如果只要求我们删除一个数字，从左到右，有 4，2，5三个选择。我们将每一个数字和它的左邻居进行比较。从 2 开始，2 小于它的左邻居 4。假设我们保留数字 4 ，可能的组合都以 4 开头。如果我们保留数字 2 ，可能的组合都以 2 开头，显然小于 4 开头的组合，我们应该删除数字 4 。
我们可以得到删除一个数字的贪心策略：
在一个序列中，如果发现前一个数字大于后一个数字，删除前一个数字；如果没有，则删除序列中最后一个数字。
我们可以对序列执行 k 次这个策略，最后就可得到结果。
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
| class Solution {
public String removeKdigits(String num, int k) {
StringBuffer sb = new StringBuffer(num);
for(int i = 1; i < sb.length() && k > 0; i++){
if(sb.charAt(i - 1) > sb.charAt(i)){
sb.deleteCharAt(i - 1);
i = 0;
--k;
}
}
if(k > 0 && k <= sb.length()){
sb.delete(sb.length() - k, sb.length());
}
int index = 0;
while(index < sb.length() && sb.charAt(index) == '0'){
++index;
}
sb.delete(0, index);
return sb.length() == 0 ? "0" : sb.toString();
}
}
|
时间复杂度O(NK)，N 为 num 序列长度，K 为要删除的数字个数。
空间复杂度O(N)，N 为 StringBuffer 空间。
我们可以使用单调栈来加速删除的过程，栈中的元素代表截止到当前位置，删除不超过 k 个数字后，所能得到的最小整数。根据之前的讨论：在使用 k 个删除字数前，栈中的序列从栈底到栈顶单调不减。
对于每个数字，如果该数字小于栈顶元素，我们就不断地弹出栈顶元素，直到
- 栈为空
- 新的栈顶元素不大于当前数字
- 我们已经删除了 k 位数字
上述步骤结束后我们还需要进行额外的处理：
- 我们删除了 m 个数字 且 m < k，需要删除序列尾部的 k - m 个数字
- 需要删除前导 0
- 如果最后序列为空，应该返回 0
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
30
31
32
|
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> deque = new LinkedList<Character>();
int length = num.length();
for(int i = 0; i < length; i++){
char digit = num.charAt(i);
while(!deque.isEmpty() && k > 0 && deque.peekLast() > digit){
deque.pollLast();
--k;
}
deque.offerLast(digit);
}
for(int i = 0; i < k; i++){
deque.pollLast();
}
StringBuffer ret = new StringBuffer();
boolean leadingZero = true;
while(!deque.isEmpty()){
char digit = deque.pollFirst();
if(leadingZero && digit == '0'){
continue;
}
leadingZero = false;
ret.append(digit);
}
return ret.length() == 0 ? "0" : ret.toString();
}
}
|
时间复杂度O(N)，N 为 num 序列长度，尽管存在嵌套循环，但最坏情况为删除序列全部数字，时间复杂度为 2N。
空间复杂度O(N)，N 为 StringBuffer 空间。