漫画：删去k个数字后的最小值

本期封面作者：蒲公英

————— 第二天 —————

什么意思呢？让我们举几个栗子：

给定整数1593212，删去3个数字，新整数的最小情况是1212

给定整数30200，删去1个数字，新整数的最小情况是200

给定整数10，删去2个数字，新整数的最小情况是0

需要注意的是，给定的整数大小可以超过long类型的范围，所以需要用字符串来表示。

————————————

我们来举一个栗子：

给定整数 541270936，要求删去一个数，让剩下的整数尽可能小。

此时，无论删除哪一个数字，最后的结果都是从9位整数变成8位整数。既然同样是8位整数，我们显然应该优先把高位的数字降低，这样对新整数的值影响最大。

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

在咱们这个例子中，数字5右侧的数字4小于5，所以删除数字5，最高位数字降低成了4。

/**
 * 删除整数的k个数字，获得删除后的最小值
 * @param num  原整数
 * @param k  删除数量
 */
public static String removeKDigits(String num, int k) {
    String numNew = num;
    for(int i=0; i<k; i++){
        boolean hasCut = false;
        //从左向右遍历，找到比自己右侧数字大的数字并删除
        for(int j=0; j<numNew.length()-1;j++){
            if(numNew.charAt(j) > numNew.charAt(j+1)){
                numNew = numNew.substring(0, j) + numNew.substring(j+1,numNew.length());
                hasCut = true;
                break;
            }
        }
        //如果没有找到要删除的数字，则删除最后一个数字
        if(!hasCut){
            numNew = numNew.substring(0, numNew.length()-1);
        }
        //清除整数左侧的数字0
        numNew = removeZero(numNew);
    }
    //如果整数的所有数字都被删除了，直接返回0
    if(numNew.length() == 0){
        return "0";
    }
    return numNew;
}
private static String removeZero(String num){
    for(int i=0; i<num.length()-1; i++){
        if(num.charAt(0) != '0'){
            break;
        }
        num = num.substring(1, num.length()) ;
    }
    return num;
}
public static void main(String[] args) {
    System.out.println(removeKDigits("1593212",3));
    System.out.println(removeKDigits("30200",1));
    System.out.println(removeKDigits("10",2));
    System.out.println(removeKDigits("541270936",3));
}

小灰的代码使用了两层循环，外层循环基于删除次数（k），内层循环从左到右遍历所有数字。

当遍历到需要删除的数字时，利用字符串的自身方法subString() 把对应数字删除，并重新拼接字符串。

显然，这段代码的时间复杂度是O（kn）。

结果，提交以后......

翻译过来就是：恭喜你，打败了16.56%的小伙伴！

1.每一次内层循环，都需要从头遍历所有数字

比如给定的整数是 11111111111114132，我们在第一轮循环中，需要遍历大部分数字，一直遍历到数字4，发现4>1，从而删除4。

以目前的代码逻辑，下一轮循环中，我们要从头开始遍历，再次重复遍历大部分数字，一直遍历到数字3，发现3>2，从而删除3。

事实上，我们应该停留在上一次删除的位置继续进行比较。而不是从头开始。

2.subString方法本身性能不高

subString方法的底层实现，涉及到了新字符串的创建，以及逐个字符的拷贝。这个方法自身的时间复杂度是O（n）。

因此，我们应该避免在每删除以后数字后就调用subString方法。

/**
 * 删除整数的k个数字，获得删除后的最小值
 * @param num  原整数
 * @param k  删除数量
 */
public static String removeKDigits(String num, int k) {
    //新整数的最终长度 = 原整数长度 - k
    int newLength = num.length() - k;
    //创建一个栈，用于接收所有的数字
    char[] stack = new char[num.length()];
    int top = 0;
    for (int i = 0; i < num.length(); ++i) {
        //遍历当前数字
        char c = num.charAt(i);
        //当栈顶数字大于遍历到的当前数字，栈顶数字出栈（相当于删除数字）
        while (top > 0 && stack[top-1] > c && k > 0) {
            top -= 1;
            k -= 1;
        }
        //遍历到的当前数字入栈
        stack[top++] = c;
    }
    // 找到栈中第一个非零数字的位置，以此构建新的整数字符串
    int offset = 0;
    while (offset < newLength && stack[offset] == '0') {
        offset++;
    }
    return offset == newLength? "0": new String(stack, offset, newLength - offset);
}

public static void main(String[] args) {
    System.out.println(removeKDigits("1593212",3));
    System.out.println(removeKDigits("30200",1));
    System.out.println(removeKDigits("10",2));
    System.out.println(removeKDigits("541270936",3));
}