《漫画算法》笔记——给定数，求删除k个数字后的最小值

  /**
     * 题目：给定一个数，求 删除k个数字后的最小值
     * 思路：考虑 “如何删除一个数字，得到最小值”，
     * 不难想到，应该优先删除“靠前，值大”的数字，
     * 观察到：如果一个数字大于它右边的那个数字，那么删除它并让自己右边的数顶替上来，必然能够降低整体的数值；
     * 综上分析，可知：从左向右遍历，找到第一个“自己右边比自己小”的数字
     */

public static void main(String[] args) {
        System.out.println(removeKDigits2("1000270936",1));
    }

    public static String removeKDigits2(String s,int k){
        String res=s;


        for (int i = 0; i < k; i++) {// 准备删除第i+1个数，只删除一个数
            boolean hasCut=false;// 检查 在res[0,...,res.len-2]中的字符是否被删除
            for (int j = 0; j < res.length()-1; j++) {
                if(res.charAt(j)>res.charAt(j+1)){
                    hasCut=true;
                    res=res.substring(0,j)+res.substring(j+1);
                    break;
                }
            }
            if(!hasCut){// 在res[0,...,res.len-2]中的字符都没有被删除，那么删除最后一个字符
                res=res.substring(0,res.length()-1);
            }
            res=removeLeft0s(res);// 删完一个数后，检查左边的0

        }
        
        if(res.length()==0){// 删完了，我觉得没必要加啊
            return "";
        }
        return res;
    }

    private static String removeLeft0s(String res) {
        int i=0;
        for(;i<res.length();i++){
            if(res.charAt(i)!='0'){
                break;
            }
        }
        return res.substring(i);
    }

上述代码实现的缺点：

1. 每次删除一个字符，都从剩余字符串的头部开始遍历，这样之前做的“是否存在逆序”检查结果就浪费了。比较节省的思路是，应该考虑接住上次检查的结果，继续进行。
2. .substring()的底层实现比较费：创建新字符串，并逐个复制字符。
   基于这些缺点，提出使用栈实现上述的思路。具体地，每次遍历到一个新字符，检查它是否大于栈顶，如果是，那么直接把这个新字符压入栈；如果否，那么弹出栈顶（表示删除这个栈顶字符，更新删除次数）。

• 下面的代码借助char[] stack和int top实现了栈的功能，（之所以这样做，我想，是因为后续方便打印出结果）、使用int offset标记第一个非零数字的位置。

 public static String removeKDigits3(String s,int k){
        int slen=s.length();
        char[] stack=new char[slen-k];// stack, ready to store the remaining nums
        int top=0;
        for (int i = 0; i < slen; i++) {
            char c=s.charAt(i);
            while (k>0&&top>0&&stack[top-1]>c){ // !! 栈顶元素是stack[top-1]
                top--;
                k--;
            }
            stack[top++]=c;
        }

        int offset=0;// 记录第一个非零数字的位置
        for (int i = 0; i < stack.length; i++) {
            if(stack[i]!='0'){
                break;
            }
            offset++;

        }
//        System.out.println(stack);
        return offset==stack.length?"0":new String(stack,offset,stack.length-offset);
    }