【leetcode】402 Remove K Digits

发表于 | 分类于 ，

除去 K 个数字后最小值


描述

给定一个非负整数num表示为一个字符串，从数字中删除k个数字，以便新的数字是最小的可能。

样例

样例1

1
2
输入: num = "1432219", k = 3
输出: "1219"

样例2

1
2
输入: num = "10200", k = 1
输出: "200"

样例3

1
2
输入: num = "10", k = 2
输出: "0"

思路

emm，想计算每个数的逆序数，然后逆序数大的移除，遇到的问题是处理很繁琐，而且还要考虑0的存在。参考了一份代码，尝试理解一下，可以理解为从已有的数字中选择出一些数字重新组合，这个过程肯定要选择小一些的数字，但是又不可能从全部数字中选择，下面这段代码 idx 和 i 的理解很关键，i 可以理解为选取的数字数目，但选择哪一个还是以 idx 来控制。

代码

c++推荐代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string removeKdigits(string num, int k) {
        int len = num.size();
        int idx = 0;
        string result="";
        for (int i = 0; i < len - k; i++) {
            int min_idx = idx;
            for (int j = min_idx; j <= i + k; j++) {
                if (num[min_idx] > num[j]) { min_idx = j; }
            }
            if (!(result.empty() && num[min_idx] == '0')) {
                result.push_back(num[min_idx]);
            }
            idx = min_idx + 1;
        }
        if (result.empty()) { result = "0"; }
        return result;
    }
};

参考

原题链接