题目描述

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

注意:

• num 的长度小于 10002 且 ≥ k。

• num 不会包含任何前导零。

样例

Example 1:

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


Example 2:

输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。


Example 3:

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

算法1

(贪心) $O(n)$

思路：尽可能让最高位小，最高位相同的情况下尽可能让次高位小，所以应该维护一个非递减栈。

1. 构建一个非递减栈$stk$：从左往右遍历数字$num$，依次进栈；每个数字$x$进栈前检查
   是否比栈顶，是的话弹掉栈顶；全部数字一共有k次机会弹栈顶（相当于，最多在这一步删掉k个数字）

2. 如果k次(删数字的)机会没有用完，则弹出栈顶直到$stk$中剩余$stk.size()-k$个数字

3. 将$stk$倒出来再reverse，统计前导0的个数，并以此返回对应的值

举例，在Example 1中，输入为 num = “1432219”, k = 3，输出为”1219”。

• 第一步，构造$stk$的步骤是, (stk=1,k=3) –> (stk=14,k=3) –> (stk=13,k=2) –> (stk=12,k=1) –> (stk=122,k=1) –> (stk=12,k=0) –> (stk=121,k=0) –> (stk=1219,k=0)

• 第二步，k已经等于0了

• 第三步，(stk=1219) –> (res=”9121”) –> (res=”1219”) –> i=0，res.substr(i)=”1219“

相关语法小细节：最后return调用的res.substr(i)

• string.substr(start , [length]) ：返回一个从指定位置开始的指定长度的子字符串

• string.substring(start, end) ：返回位于 String 对象中指定位置的子字符串。

C++ 代码

class Solution {
public:
    string removeKdigits(string num, int k) {
        stack<char> stk;
        for (auto x : num)
        {
            while (stk.size() && stk.top() > x && k)
            {
                stk.pop();
                k--;
            }
            stk.push(x);
        }

        while (k -- ) stk.pop();

        string res;
        while (stk.size())
        {
            res += stk.top();
            stk.pop();
        }
        reverse(res.begin(), res.end());
        int i = 0;
        while (i < res.size() && res[i] == '0') i++;
        if (i == res.size()) return "0";
        return res.substr(i);
    }
};

作者：yxc
链接：https://www.acwing.com/activity/content/code/content/13004/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。