LeetCode 402 移掉k位数字

LeetCode 402 移掉k位数字

https://leetcode-cn.com/problems/remove-k-digits/

这是一道使用单调栈解决的贪心算法。

我们首先把贪心策略给弄清楚，这道题的力扣官方题解提供了详细的解释。总结一句话就是说要想移除k位数字之后剩下的数字最小，则需要保证靠前的数字尽可能小。举个例子，比如输入num = "12345264", k = 4,如下图所示。

我们从左到右依次将输入的数字入栈，在入栈之前需要确保栈顶数字始终比将要入栈的数字更小。如上图所示，当遇到第二个2时，我们发现栈顶的5比2大，于是将5出栈，k自减1变成了3。随后，栈顶的4仍然比2大，于是将4出栈，k自减后变成了2。这样不断出栈，直到栈顶的数字不再大于2，然后再将2入栈。同样的道理，在遇到最后一个数字4时，我们需要将栈顶的6出栈，此时k自减为0，不再需要移除数字了。输出最后的结果1224，算法结束。

使用单调栈解决本题的代码如下。需要注意的地方有两个，一个是移除k位数字之后，栈可能为空；另一个是得记得移除前导0，并且移除之后还得判断ans的长度是否为0，为0则返回字符串“0”，否则返回移除前导0之后剩余的部分字符串。

class Solution {
public:
    string removeKdigits(string num, int k) {
        // 单调栈走一遍
        stack<char> stk;
        for (char c : num) {
            while (k > 0 && !stk.empty() && c < stk.top()) {
                stk.pop();
                --k;
            }
            stk.push(c);
        }

        // 确保去掉了k位数字
        while (k > 0 && !stk.empty()) {stk.pop(); --k;}

        // 特例 - 栈为空
        if (stk.empty()) return "0";

        // 将剩余数字取出
        string ans;
        while (!stk.empty()) {
            ans += stk.top();
            stk.pop();
        }
        reverse(ans.begin(), ans.end());

        // 去掉前导0
        int i;
        for (i = 0; i < ans.size() && ans[i] == '0'; ++i) ;

        if (i >= ans.size()) return "0";
        else return ans.substr(i, ans.size() - i);
    }
};