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

本文主要是介绍《漫画算法》笔记——给定数，求删除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);}

上述代码实现的缺点：

每次删除一个字符，都从剩余字符串的头部开始遍历，这样之前做的“是否存在逆序”检查结果就浪费了。比较节省的思路是，应该考虑接住上次检查的结果，继续进行。
.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 numsint 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);}