删去k个数字后的最小值

未分类 3天前程序员胖胖胖虎阿

11 0 0

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

代码

第一版

```java
/**
     * 删除整数的k个整数，获取函数后的最小值
     *
     * @param num 原整数
     * @param k   删除数量
     * @return 最小值
     */
    public static String removeKDigits(String num, int k) {
        String newNum = num;
        for (int i = 0; i < k; i++) {
            boolean hasCut = false;
            //每次移除一位，保证当前步，移除1位的最小值
            for (int j = 0; j < newNum.length() - 1; j++) {
                //char类型 在java里可以直接比较
                if (newNum.charAt(j) > 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 < num.length()-1; i++) {
            if (num.charAt(0) != '0')
                break;
            num = num.substring(1);
        }
        return num;
    }

    public static void main(String[] args) {
        System.out.println(removeKDigits("1593210", 3));//1210
        System.out.println(removeKDigits("301200", 1));//1200
        System.out.println(removeKDigits("20", 2));//0
        System.out.println(removeKDigits("5674201", 3));//4201
    }
```

第二版

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

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

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

```java
/*
* 删除整数的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 < num.length(); i++) {
char c = num.charAt(i);//当前位数字字符
//finalChar[top - 1]代表的是上一位，c是当前位
while (top > 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 < newLen && finalChar[offset] == '0')//获取最后字符数组中，首个不等于0字符的数字的索引，即是移除最后数字的左边的0
offset++;
```
    return offset == newLen ? "0"
            : new String(finalChar,offset,newLen - offset);
    //使用new String(finalChar,offset,newLen - offset)，是为了去掉，左侧的'0'，和创建字符数组时的默认值'0'
}

public static void main(String[] args) {
    System.out.println(removeKDigits("1593210", 3));//1210
    System.out.println(removeKDigits("301200", 1));//1200
    System.out.println(removeKDigits("20", 2));//0
    System.out.println(removeKDigits("5674201", 3));//4201
}
```
```