402. 移掉 K 位数字

题目

原题 402. 移掉 K 位数字

解题

思考一下该使用什么样的策略去移除数字会让最终的数字尽可能的小：保证高位数字一定要尽可能的小，那么最终得到的数字就是最小的数字。本质上我们可以维护一个单调栈去实现这个策略。

注意事项

1. 单调栈在维护的过程中，可能过早的消耗完 k 个可以被删除的字符，也可能没有完全消耗掉 k 个字符
2. 针对 k 没有被全部消耗的情况，我们从后向前去删除单调栈就行，直到 k 个可以被删除的字符用光
3. 对于可能出现开头 0 的场景，进行一个后处理就可以了。

单调栈

    public String removeKdigits(String num, int k) {
        StringBuilder sb = new StringBuilder();
        sb.append(num.charAt(0));
        for(int i = 1; i < num.length(); i++) {
            char ch = num.charAt(i);
            // 维护单调栈, 当 k==0 时我们就无法继续维护单调栈的递增性质，直接入栈
            while (!sb.isEmpty() && ch<sb.charAt(sb.length()-1) && k > 0) {
                sb.deleteCharAt(sb.length()-1);
                k--;
            }
            sb.append(ch);
        }
        // 去除首个 0
        while (!sb.isEmpty() && sb.charAt(0)=='0'){
            sb.deleteCharAt(0);
        }
        // 未消耗完 k
        while (!sb.isEmpty() && k>0){
            sb.deleteCharAt(sb.length()-1);
            k--;
        }
        return sb.isEmpty() ?"0":sb.toString();
    }