LeetCode 402. 移掉K位数字

题目描述

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。

示例一
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例二
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例三
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
https://leetcode-cn.com/problems/remove-k-digits/

思路

num = ”1234321“，k = 1，毫无疑问，当我们把数4删除掉时，得到的是最小的数字，我们发现”1234“是单调递增的，当”12343“时就不再是增的，那么我们把”4“删除，就可以变成最小的了，那这是不是一个特例呢？我们再往下看样例
num = "1432219" , k = 3
1432219 “43”位置递减，将4删掉
132219 “32”位置递减，将3删掉
12219 “21”位置递减，将2删掉
最后结果1219
　　这说明从左到右找到第一个递减的位置，将前面的大数删掉的贪心思想是正确的，但是还有一种特殊的情况，num="123456789"，整个数字全部是递增的，我们完全可以看出来，只需要把末尾删除即可。同时还要注意，不能有前导0，即”0220“，在最后的数字处理中要把前导0删掉，即”200“

代码

 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()&&k>0&&now<stack.peek()){
                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 sb=new StringBuilder();
        while(!stack.isEmpty())
            sb.append(stack.pop());
        //从后往前添加所以我们要逆序
        return sb.reverse().toString();
    }