题目描述

给定一个以字符串表示的非负整数 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。

算法1

(暴力枚举) $O(n^2)$

1.从左至右扫描，当前扫描的数还不确定要不要删，入栈暂存，保留对它的记忆。
2.123531这样「高位递增」的数，肯定不会想删高位，高位肯定想尽量小，会尽量删低位。因为大的数都在低位,所以如果我们删除了高位的k 个数,那么得出来的数只会比删除低位的k 个数更大.所以当遇到递增的序列时,删除低位的数.
3.同理,432135这样「高位递减」的数，删除高位的k 个数的结果会比删除k 个低位的数的结果要小。

所以思路就是:如果当前的数比前一个数(高位数)小,那么就应该把前一个数给删除掉,再加上当前数.如果当前数比前一个数(高位数)大,说明此时低位数比高位数要大,那么就应该删除低位数.

此时应该想到一个数据结构:栈,栈这个数据结构能够记忆前一个数并且能够操作前一个数。

特殊情况: 如果当前数是0,并且此时栈中没有数的话,这个0 应该忽略.

时间复杂度

O(n)

参考文献

https://leetcode-cn.com/problems/remove-k-digits/solution/wei-tu-jie-dan-diao-zhan-dai-ma-jing-jian-402-yi-d/

Java 代码

   public String removeKdigits(String num, int k) {
        if(num.length() == k) return "0";
        StringBuffer stack = new StringBuffer();

        for(int i = 0; i < num.length(); i++){
            char ch = num.charAt(i);

            while(k > 0 && stack.length() > 0 && stack.charAt(stack.length()-1) > ch){
                stack.deleteCharAt(stack.length() - 1);
                k --;
            }

            if(ch == '0' && stack.length() == 0){
                continue;
            }
            stack.append(ch);
        }
        //有可能num 在某一段是一个单调递增的序列,所以此时无法进入到上面的while 循环中
        //而递增的序列: 去掉高位 > 去掉低位的.例如: num = "123" k = 1 , "23" > "12"
        //因为大的数都在低位,而小的数都在高位,所以一定要删除k 个数的话,从低位开始删(把大的数都删掉)是最好的。
        while(k > 0 && stack.length() > 0){
            stack.deleteCharAt(stack.length() - 1);
            k --;
        }


        return stack.length() < 1? "0" : stack.toString();
    }