402. 移掉K位数字

题目描述

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

思路

贪心

删掉前k个字符中的最大字符，删k次。

错误样例123， k = 1

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
class Solution {
public:
    string removeKdigits(string num, int k) {
        int n = num.size();
        vector<int> visit(n);
        auto cmp = [](pair<char, int>& x, pair<char, int>& y) {
            return x.first < y.first;
        };
        priority_queue<pair<char,int>, vector<pair<char, int>>, decltype(cmp)> q(cmp);
        int i = 0, cnt = 0;
        while(i < n || cnt < k) {
            if(i < k) {
                q.emplace(num[i], i);
            } else if(cnt < k) {
                auto t = q.top();
                q.pop();
                visit[t.second] = 1;
                ++cnt;
                if(i < n)
                q.emplace(num[i], i);
            }
            ++i;
        }
        
        string res;
        bool flag = false;
        for(int i = 0;i < n;++i) {
            if(!visit[i]) {
                if(!flag && num[i] != '0') {
                    flag = true;
                }
                if(flag)
                    res.push_back(num[i]);
            }
        }
        return res.size() > 0?res:"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) {
        int n = num.size();
        if(n == 0) return "0";
        vector<char> s;
        int i = 1, j = 0;
        s.push_back(num[0]);
        while(i < n) {
            while(j < k && !s.empty() && num[i] < s.back()) {
                s.pop_back();
                ++j;
            }
            s.push_back(num[i]);
            ++i;
        }
        while(j < k) {
            s.pop_back();
            j++;
        }
        
        string res;
        bool flag = false;
        for(int i = 0;i < s.size();++i) {
            if(!flag && s[i] != '0') {
                flag = true;
            }
            if(flag) res.push_back(s[i]);
        }
        return res.size() > 0? res: "0";
    }
};