LeetCode 402 移掉k位数字

LeetCode 402 移掉k位数字

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

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

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

我们从左到右依次将输入的数字入栈,在入栈之前需要确保栈顶数字始终比将要入栈的数字更小。如上图所示,当遇到第二个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);
    }
};
上一篇:基于机器学习和TFIDF的情感分类算法,详解自然语言处理


下一篇:使用 Colab 在 tf.keras 中训练模型,并使用 TensorFlow.js 在浏览器中运行