题目描述

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

题意：给一个数字，让你从中删除k个字符，使得剩下的数去掉前导0后最小。

算法1

(单调栈，贪心)

题解：如果我们当前遇到的数字比上一个数字要小的话，肯定是删除上一个数字比较划算。我们最多能删除k个字符。所以我们使用一个单调栈来存储每一个字符，如果当前读进来的数字比前一个数字小，我们就将栈顶元素出栈，直至出栈了k个字符或者栈顶元素已经比当前元素还小。这样在我们删除k个元素后，栈中元素就是剩下的数字啦。这时候我们需要考虑的就是删除前导0和空栈的情况啦。字符串有push和pop操作，所以我们可以直接用字符串来模拟栈，效果是一样的。

    string removeKdigits(string num, int k) {
        string res;
        for(auto x : num)
        {
            while(res.size() > 0 && x < res.back() && k > 0) 
            {
                res.pop_back();
                k --;
            }
            res.push_back(x);
        }
        while(k > 0){res.pop_back();k --;}
        int n = res.size(),i = 0;
        while(res[i] == '0') 
            i ++;
        return n - i == 0?"0":res.substr(i,n - i);
    }