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);
}
};