删除k个数字后的最小值——小米OJ

描述 有一行由 N 个数字组成的数字字符串，字符串所表示的数是一正整数。移除字符串中的 K 个数字，使剩下的数字是所有可能中最小的。

假设：

字符串的长度一定大于等于 K 字符串不会以 0 开头 输入 一行由 N 个数字组成的数字字符串（0 < N < 20），和一个正整数 K（K < N），两个数据由空格隔开，如：1432219 3。

输出 移除 K 位后可能的最小的数字字符串。 如 1432219 移除 4, 3, 2 这 3 个数字后得到 1219，为所有可能中的最小值。

mport java.util.*; public class Main { public static void main(String args[]) { Scanner scan = new Scanner(System.in); String line; while (scan.hasNextLine()) { line = scan.nextLine().trim(); String[] arr = line.split(" "); int k = Integer.parseInt(arr[1]); String numNew = arr[0]; while (k != 0){ boolean flag = false; for (int i = 0; i < numNew.length() - 1; i++) { if(numNew.charAt(i) > numNew.charAt(i+1)){ 从左向右遍历，找到比自己右侧数字大的数字并删除 numNew = numNew.substring(0,i) + numNew.substring(i+1, numNew.length()); flag = true; break; } } if(!flag){ //删除最后一个数 numNew = numNew.substring(0, numNew.length()-1); } //清除整数左侧为0的数 //numNew = removeZero(numNew); k--; } int index = 0; for(int i = 0; i < numNew.length(); i++){ if(numNew.charAt(i) != '0'){ index = i; break; } } System.out.println(numNew.substring(index)); } } }

改进

package test.com; public class StackTo_Delete_K_Value { /** * 借助于辅助栈实现 * 时间复杂度为O(kN) * 空间复杂度为O(N) */ public static String backNum(String num, int k){ String numNew = num; //创建栈 int numLength = num.length() - k; //数的长度。最后从栈中，以栈底为起点截取numLength个数字(其中可能包含第一个为0的数，需要后面进一步判断) char[] stack = new char[num.length()]; //栈的长度和数的长度一致，防止索引越界的情况 int top = 0; //boolean flag = false; for (int i = 0; i < num.length(); ++i) { char c = numNew.charAt(i); while (top > 0 && stack[top-1] > c && k > 0){ //如果左边的数字大于右边的数字，则弹栈 top -= 1; k--; //flag = true; } stack[top++] = c; //注意索引越界异常 } int offset = 0; //从栈低开始找出第一个不为0的数，构建字符串数字 for (int i = 0; i < stack.length; i++) { if(stack[i] != '0') offset = i; break; } return new String(stack, offset, numLength - offset); } public static void main(String[] args) { String num = "541270396"; System.out.println(backNum(num, 3)); System.out.println("---------------"); String num2 = "55554"; System.out.println(backNum(num2, 1)); String num3 = "55555"; System.out.println(backNum(num3, 1)); System.out.println("---------------"); } }

编程语言 Java - OpenJDK 1.8.0 结果 通过 最大执行时间 85.45 ms 最大内存开销 21664 KiB 判题信息 运行时间打败了 100% 的 Java 8 玩家！