欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【LeetCode-402】402.移除k位数字(给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。)

程序员文章站 2022-07-02 10:17:25
...

移除k位数字

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

【LeetCode-402】402.移除k位数字(给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。)
【LeetCode-402】402.移除k位数字(给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。)

思路:单调栈(贪心+栈)

class Solution {
    
    /*
    单调栈的另一个应用,思想为删除靠前的较大的数能够使得最后的数值最小。 构建递增栈,若当前数字小于栈顶元素,则在满足待删减字符数不为0的情况下,栈顶元素出栈,当前数字入栈。
    */
    public String removeKdigits(String num, int k) {
         //贪心算法+单调栈
        if(k >= num.length() || num.length() == 0) {
            return "0";
        }
        //栈顶始终是最大值    
        Stack<Integer> stack = new Stack<>();
        stack.push(num.charAt(0) - '0');
        
        for(int i = 1; i < num.length() ; i++) {
            int now = num.charAt(i) - '0';
            //可能好几个值都比当前值大,那么我们就在k允许的情况下,去去除它。
            while(!stack.isEmpty() && stack.peek() > now && k > 0) {
                stack.pop();
                k--;
            }
            //不等于0可以添加进去,
            //等于0,栈不为空可以填进去,
            if(now != 0 || !stack.isEmpty()) {
                stack.push(now);
            }
            
        }
        
        //56789这种情况,前面一直比后面小,那就去除栈顶,谁让栈顶最大
        while(k > 0) {
            k--;
            stack.pop();
        }
        
        //10,1(当now=0时,满足条件,去掉1,但now为0,且为空。)
        if(stack.isEmpty()) {
            return "0";
        }
        
        StringBuilder res = new StringBuilder();
        while(!stack.isEmpty()) {
            res.append(stack.pop());
        }
        
        //从后往前添加,所以我们要逆序
        return res.reverse().toString();
    }
    
}

扩展:相似的题

321.拼接最大数