Keshawn_lu's Blog

Leetcode 402. 移掉K位数字

字数统计: 670阅读时长: 2 min
2020/11/15 Share

题目简介:

给定一个以字符串表示的非负整数 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。

思路:

由于移除数字后需要得到尽可能小的数字,所以在最前面的数字越小越好。

我们可以先用移除一位数字作为例子,如253,当num[2] = 3 < num[1] = 5时,我们便可以将5删除,留下的便是最小的数字23

换句话说,也就是当num[i] < num[i - 1]时,我们便可以将num[i - 1]删除,否则排在前面的便是num[i],整体就变大了。

那么问题转化为移除k位数字时,做法也是一样的,这时我们需要利用栈。

当前元素小于栈顶元素时,即num[i] < num[i - 1]时,我们便可以弹出栈顶元素,相当于删除了一个数字(前提是栈非空且k > 0)。

遍历完字符串后,若k > 0,则我们需要比较k与字符串res的长度:

  • k >= res.size(),说明所有数字都需要被删除,则res = "0"
  • k < res.size(),则将字符串最前面的元素删除,也就是将栈顶元素删除(栈顶元素为最大数字)。

最后将字符串翻转,并去除前导0即可。

tip:

  • 入栈时需要将所有字符都入栈。

代码如下:

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
string removeKdigits(string num, int k) {

string res;
stack<char> stk;

stk.push(num[0]);

int i = 1;
while(i < num.size()){

while(k > 0 && !stk.empty() && num[i] < stk.top()){

stk.pop();
k--;
}

stk.push(num[i]);
i++;
}

while(!stk.empty()){

res += stk.top();
stk.pop();
}

if(k > 0){ //没有完全删除的情况

if(k >= res.size()) //字符串需要全部删除
res = "0";
else
res = res.substr(k, res.size()); //去除最前面的数字
}

reverse(res.begin(), res.end()); //删除完再翻转

if(res[0] != '0')
return res;

//去除前导0
i = 0;
while(res[i] == '0' && i < res.size() - 1) //至少为0,留一位
i++;

res = res.substr(i, res.size());

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: