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. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网