8.删去k个数字后的最小值

题目

给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数经可能小。应该如何选取被去掉的数字？

其中整数的长度大于或等于k，给出的整数的大小可以超过long类型的数字范围。

举例：整数1593210，删除3个数字，新整数最小为1210；整数5674201，删除3个数字，新整数最小值为4210。

思路

上例：整数1593210，要求删除1个数字，找出最小的整数。

此时，无论删除那个数字，结果都是从7位整数，变为6位整数。既然都是6位整数，显然优先将高位的数字降低，这样对新整数的值影响最大。

但是不代表，优先删除最高位的整数，例如1593210，如果移除最高位1，结果是593210，这不是最小值，因为有193210就比593210小。

这删除一位的分析，最小值，能直接看出来，移除9是最小的，153210。但是计算机，是不能看的，所以要找出，删除一位时的规律，才能写程序。

还是1593210，删除9得到最小值的规律。很简单，把原整数的所有数字从左到右进行比较， 如果发现某一位数字大于它右面的数字，那么在删除该数字后，必然会使该数位的值降低，因为右面比它小的数字顶替了它的位置。

1593210，删除3位的最小值。按照规律，移除9 -> 153210，移除5 -> 13210，移除3 -> 1210，1210为最小值。

这样依次求得局部最优解，最终得到全局最优解的思想，叫作贪心算法。10549

代码

第一版

    /**
     * 删除整数的k个整数，获取函数后的最小值
     *
     * @param num 原整数
     * @param k   删除数量
     * @return 最小值
     */
    public static String removeKDigits(String num, int k) {
        String newNum = num;
        for (int i = 0; i  newNum.charAt(j + 1)) {
                    newNum = newNum.substring(0, j) + newNum.substring(j + 1);//substring(i),等于substring(i,str.length())
                    hasCut = true;
                    break;
                }
            }
            //从左往右遍历，未找到左位大于右位的数字，移除最后一位
            if (!hasCut)
                newNum = newNum.substring(0, newNum.length() - 1);//substring(i,j)截取范围是[i,j),i,j代表的是索引
            newNum = removeZero(newNum);//移除整数左侧的数字0
        }
        if (newNum.length() == 0)
            return "0";//所有数字都被删除，返回字符串0
        return newNum;
    }

    private static String removeZero(String num) {
        for (int i = 0; i 

第二版

上述代码，使用了2层循环，外层循环次数，就是删除的数字个数k，内存从左到右遍历所有数字。符合条件(当前位大于后一位)的数字，利用substring()函数，截取字符串，构成新字符串。代码复杂度O(kn)。

代码的功能实现正常，但是性能不好。

• 每次都从左往右遍历，但是因为每次删除是删除的首个满足条件的数字，所以下次，只要从上一次删除的位置开始往右遍历即可。
• substring()底层实现，涉及到新字符串的创建，以及字符的逐个赋值。这个方法的时间复杂度是O(n)。因此应该，避免每删除一个数字，就调用substring方法。

    /**
     * 删除整数的k个整数，获取函数后的最小值
     *
     * @param num 原整数
     * @param k   删除数量
     * @return 最小值
     */
    public static String removeKDigits(String num, int k) {
        int newLen = num.length() - k;
        //使用原字符串的长度，可能会有冗余，但是是为了满足对于k==num.length()的情况，finalChar也能保存字符
        char[] finalChar = new char[num.length()];//默认值是'0'
        int top = 0;
        for (int i = 0; i  0 && finalChar[top - 1] > c && k > 0) {
                top--;//保证在finalChar字符数组，当前位字符，替换左边一位
                k--;//删除次数迭代
            }
            //top>0保证，首位一定会进入到finalChar字符数组
            finalChar[top++] = c;//先进行finalChar[top] = c赋值操作，再进行top=top+1操作
        }
        int offset = 0;//偏移量
        while(offset