[PHP知识库]删除k个数字后的最小值

????????比如给出一个整数541270936，要求删去一个数字，让剩下的整数尽可能小。此时无论删除哪一个数字都是变成8位数，显然应该优先把高位的数字降低，这样对新整数的值影响最大。

????????把原整数的所有数字从左到右进行比较，如果发现某一位数字大于它右边的数字，那么在删除该数字后，必然会使该数位的值降低，因为右面比他小的数字顶替了它的位置。

对于541270936，删除3个数字，第一个就是先删除5，第二个4，第三个7，得120936.

注：

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

开始思路不太多，就当学习和了解贪心算法，就看了一眼代码的实现，有以下点

1.字符串

2.找到就删除一次的开关

3.没找到就删除最后一个

4.清除左侧数字0

5.所有整数都被删除返回0

自己花了20min才写出从左至右删除k个数字

public static String removeKDigits(String num,int k){
    //从做至右删除k个数字
    for (int i = 0; i <k ; i++) {
        boolean flag = false;//删除的开关
        for (int j = 0; j<num.length()-1; j++) {
                char[] chars = num.toCharArray();
                if (chars[j]>chars[j+1]){
                    num = num.substring(0,j)+num.substring(j+1,num.length());
                    flag=true;
                    break;
            }
        }
    }

主要是String方法又不太熟悉了，太久没有再去看，还得临时去看笔记，采用转为char数组判断再字符串拼接

然后其他的除了清除左侧数字0，真的没有想到怎么去写，其他的其实也都想到并写了

正解其实就是

附上代码：

public class DeleteKNumber {
    /**
     * 删除整数的k个数字，活得删除后的最小值
     * @param num 原整数
     * @param k 删除数量
     * @return
     */
    public static String removeKDigits(String num,int k){
        //从做至右删除k个数字
        for (int i = 0; i <k ; i++) {
            boolean flag = false;//删除的开关
            for (int j = 0; j<num.length()-1; j++) {
                    if (num.charAt(j)>num.charAt(j+1)){
                        num = num.substring(0,j)+num.substring(j+1,num.length());
                        flag=true;
                        break;
                    }
            }
          //  如果没找到要删除的数字删除最后一个
            if (!flag){
                num = num.substring(0,num.length()-1);
            }
        }
        //清楚左侧的数字0
        int start = 0;
        for (int i = 0; i < num.length()-1; i++) {
            if (num.charAt(i)!= '0'){
                break;
            }
            start++;
        }
        num = num.substring(start,num.length());

        //如果整数的所有数字都被删除了，返回0
        if(num.length()==0){
            return "0";
        }
        return num;
    }

    public static void main(String[] args) {
        System.out.println(removeKDigits("123436", 1));
        System.out.println(removeKDigits("31911", 2));
        System.out.println(removeKDigits("3200096", 2));
    }
}

继续看了之后，还有一个优化，就不用每次删除数字都从头遍历所有数字，而且subString方法本身性能不高

运用栈的特性，再遍历原整数的数字时，让所有数字一个个入栈，当某个数字需要删除时，让该数字出栈，换一个思路，以遍历数字作为小循环，以k作为内循环。

public class DeleteKNumber6 {
    /**
     * 删除整数的k个数字，获得删除后的最小值
     *
     * @param num 原整数
     * @param k   删除数量
     * @return
     */
    public static String removeDigits(String num, int k) {
        //新整数的最终长度=原整数长度-k
        int newLength = num.length() - k;
        //创建一个栈，用于接收所有数据
        char[] stack = new char[newLength];
        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;
        }
        //找到栈中第1个非零数字的位置，以此构建新的整数字符串
        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(removeDigits("1234546",1));
        System.out.println(removeDigits("320006",2));
        System.out.println(removeDigits("6541111",3));
    }
}