官方地址：https://leetcode-cn.com/problems/remove-k-digits/

问题描述

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

基本事实

1. 移除最大数无法保证移除后结果是最小的
2. 使用单调递减队列保证从左往右剩余的数字最小

单调队列解

参考：https://leetcode-cn.com/problems/remove-k-digits/solution/402-yi-diao-kwei-shu-zi-dan-diao-zhan-by-guohaodin/

class Solution {
public:
    string removeKdigits(string num, int k) {
        string res;
        int n = num.size(), m = n - k;        
        for (char c : num) {
            while (k && res.size() && res.back() > c) {
                res.pop_back();
                --k;
            }
            res.push_back(c);
        }
        res.resize(m);
        //去除前导0， 如10200，k = 1
        while (!res.empty() && res[0] == '0') {
            res.erase(res.begin());
        }
        return res.empty() ? "0" : res;
    }
};

枚举解

class Solution {
public:
    string removeKdigits(string num, int k) {
        if (k == 0) {
            return num;
        }
        if (k == num.size()) {
            return "0";
        }
        int size = num.size();
        
        int cur = 0;
        for (int removedNum = 0; removedNum < k;) {
            if (num[cur] > num[cur + 1]) {
                num.erase(cur, 1);
                removedNum ++;
                cur = 0;
            } else if (num[cur] > num[cur + 1]) {
                num.erase(cur + 1, 1);
                removedNum ++;
                cur = 0;
            } else {
                if (cur == num.size() - 1) {
                    num = num.substr(0, size - k);
                    break; 
                }
                cur ++;
            }
        }
        
        while (num[0] == '0' && num.size() > 1) {
            num.erase(0, 1);
        }
        return num;
    }
};

暴力解

#include <vector>
#include <iostream>
#include <cmath>
#define min(n1, n2) ((n1 < n2) ? n1 : n2)

using namespace std;

class Solution {
public:
    int minNum;
    int limitNumber;
    vector<int> removeElements; // 移除的第个数，值是对应的值的下标
    vector<int> nums;
    
    // 判断当前这个数是否已经移除过了
    bool isRemoved(int i, int limitRemoved) {
        for (int j = 0; j < limitRemoved; j ++) {
            if (removeElements[j] == i) {
                return true;
            }
        }
        return false;
    }
    
    void getMin() {
        vector<int> numMin;
        for (int i = 0; i < nums.size(); i ++) {
            if (isRemoved(i, limitNumber)) {
                continue;
            }
            numMin.push_back(nums[i]);
        }
        // numMin的值
        int result = 0;
        for (int i = numMin.size() - 1; i >= 0; i --) {
            result += numMin[numMin.size() - i - 1] * pow(10, i);
            // cout << "numMinone:" << numMin[numMin.size() - i - 1] << endl;
        }
        // cout << "result: " << result << endl;
        if (minNum == -1) {
            minNum = result;
        } else {
            minNum = min(result, minNum);
        }
    }
    
    // 从0位移除到最后一位
    void minPl(int currentNumber) {
        for (int i = 0; i < nums.size(); i ++) {
            if (isRemoved(i, currentNumber + 1)) {
                continue;
            }
            removeElements[currentNumber] = i;
            if (currentNumber == limitNumber - 1) {// 已经移除了limitNumber位数字
                // 计算移除后的数字的大小和min进行比较，取最小
                getMin();
            } else {
                minPl(currentNumber + 1);
            }
        }
    }
    
    string removeKdigits(string num, int k) {
        if (k == 0) {
            return num;
        }
        minNum = -1;
        limitNumber = k;
        removeElements.resize(limitNumber);
        fill(removeElements.begin(), removeElements.end(), -1);
        for (int i = 0; i < num.length(); i ++) {
            nums.push_back(num[i] - '0'); // 转成int: https://stackoverflow.com/questions/5029840/convert-char-to-int-in-c-and-c
            // cout << nums[nums.size() - 1] << endl;
        }
        
        minPl(0);
        
        // cout << minNum << endl;
        
        return to_string(minNum);
    }
};

一些注意的点

测试用例

int main(int argc, char * argv[]) {
    Solution solution;
    cout << solution.removeKdigits("1432219", 3) << endl;
    cout << solution.removeKdigits("1234567890", 8) << endl;
    cout << solution.removeKdigits("10200", 1) << endl;
    cout << solution.removeKdigits("10", 2) << endl;
    cout << solution.removeKdigits("112", 1) << endl;
    cout << solution.removeKdigits("1111111", 3) << endl;
    return 0;
}

参考资料

1. https://blog.csdn.net/zuzhiang/article/details/78134247