【LeetCode每日一题】单调栈 402 移掉k位数字-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode每日一题】单调栈 402 移掉k位数字。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

402. 移掉 K 位数字

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k **位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

示例 1 ：

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

如果有 m+1 位数字，S1

$a_0a_1a_2....a_m$

需要去掉n位数字，S2

$a_i,a_k,,,,a_n$

剩余的 m+1-n 位。S3

假如用去掉的 n 位数字中的一个数字

$a_i （a_i < a_j）$

替换剩余的 S3 里面的最大的字符 (a_j)，那么新的数字会比原来的S3 要小，因此，我们用来去掉的n位数字中的每一个数字都需要大于剩余的数字

⇒ 去掉前N个最大的数字。

⇒ 通过单调栈去掉极大值，尖峰。

经过上面的分析，我们基本可以确定需要使用栈来充当这个容器了。当遍历每一个数字的时候，如果当前数字比栈顶数字大，是递增，那么就可以直接入栈，因为下一个数字有可能比当前的大；如果当前数字比栈顶的小，那么就需要将栈顶的元素弹出删除，因为这个栈顶元素既是递增的最后一个数字，也是递减的第一个数字，是一个尖峰，再删除过程中记录删除的个数或者将k - 1，当删除了所有k个数字后，就得出了结果。

遍历完毕后，k个数字没有移除完，比如数字123456789，移除3个数字，按照上面的分析，得出的结果还是123456789，出现这种情况是因为移除部分数字后，得出的结果是一个高位递增的数，所以无法再移除了，这个时候，只要出现这种情况，将低位的数字移除掉剩余个数即可，可以仔细想想这一个特殊点文章来源地址https://www.toymoban.com/news/detail-828343.html

var removeKdigits = function(num, k) {

    if(k === num.length){
        return "0";
    }

    let stack = [];
    for(let i = 0; i < num.length; i++){
        // 遇到尖峰，去掉尖峰  || 单调递减
        while(k && stack.length && stack.at(-1) > num[i]){
            stack.pop();
            k--;
        }
        // 维护的是一个递增的栈，但是首位不能是0
        if(!(nums[i]==="0" && stack.length === 0)){
            stack.push(num[i]);
        }
    }

// 移除尖峰，如果没有尖峰，就把低位的删除即可 ||单调递增
    while(k>0 && stack.length){
        stack.pop();
        k--;
    }

    return stack.length === 0 ? "0" : stack.join("");

};