删去k个数字后的最小值
给出一个整数，从该整数中去掉k 个数字，要求剩下的数字形成的新整数尽可能小。应该如何选取被去掉的数字？
其中整数的长度大于或等于k ，给出的整数的大小可以超过long类型的数字范围。

我们来举一个例子。
给出一个整数 541270936，要求删去1个数字，让剩下的整数尽可能小。
此时，无论删除哪一个数字，最后的结果都是从9位整数变成8位整数。既然同样是8位整数，显然应该优先把高位的数字降低，这样对新整数的值影响最大。
如何把高位的数字降低呢？很简单，把原整数的所有数字从左到右进行比较，如果发现某一位数字大于它右面的数字，那么在删除该数字后，必然会使该数位的值降低，因为右面比它小的数字顶替了它的位置。
在上面这个例子中，数字5右侧的数字4小于5，所以删除数字5，最高位数字降低成了4，最后结果是41270936。
如果再删除一个数字，那么删除的数字应该是4，最后的结果是1270936。
如果在删除一个数字的话，那么应该删除的是7。
这里每一步都要求得到删除一个数字后的最小值，经历3次，相当于求出了删除k（k =3）个数字后的最小值。
像这样依次求得局部最优解 ，最终得到全局最优解 的思想，叫作贪心算法。

  1. public class RemoveKDigits {
  3.     private static String removeZero(String num) {
  4.         for (int i = 0; i < num.length() - 1; i++) {
  5.             if (num.charAt(0) != '0') {
  6.                 break;
  7.             }
  8.             num = num.substring(1, num.length());
  9.         }
  10.         return num;
  11.     }
  13.     public static String removeKDigits(String num, int k) {
  14.         String numNew = num;
  15.         for (int i = 0; i < k; i++) {
  16.             boolean hasCut = false;
  17.             // 从左向右遍历，找到比自己右侧数字大的数字并删除
  18.             for (int j = 0; j < numNew.length() - 1; j++) {
  19.                 if (numNew.charAt(j) > numNew.charAt(j + 1)) {
  20.                     numNew = numNew.substring(0, j) + numNew.substring(j + 1, numNew.length());
  21.                     hasCut = true;
  22.                     break;
  23.                 }
  24.             }
  25.             // 如果没有找到要删除的数字，则删除最后一个数字
  26.             if (!hasCut) {
  27.                 numNew = numNew.substring(0, numNew.length() - 1);
  28.             }
  29.             // 清除整数左侧的数字 0
  30.             numNew = removeZero(numNew);
  31.         }
  32.         // 如果整数的所有数字都被删除了，直接返回 0
  33.         if (numNew.length() == 0) {
  34.             return "0";
  35.         }
  36.         return numNew;
  37.     }
  39.     public static void main(String[] args) {
  40.         System.out.println(removeKDigits("1593212", 3));
  41.     }
  42. }

时间复杂度贪心算法 - 图1。

优化

  1. 每一次内层循环都需要从头开始遍历所有数字。
  2. subString方法本身性能不高。
    1. public static String removeKDigits(String num, int k) {
    2.  // 新整数的最终长度 = 原整数长度 - k
    3.  int newLength = num.length() - k;
    4.  // 创建一个栈，用于接收所有数字
    5.  char[] stack = new char[num.length()];
    6.  int top = 0;
    7.  for (int i = 0; i < num.length(); ++i) {
    8.      // 遍历当前数字
    9.      char c = num.charAt(i);
    10.      // 当栈顶数字大于遍历到的当前数字时，栈顶数字出栈（相当于删除数字）
    11.      while (top > 0 && stack[top - 1] > c && k > 0) {
    12.          top -= 1;
    13.          k -= 1;
    14.      }
    15.      // 遍历到的当前数字入栈
    16.      stack[top++] = c;
    17.  }
    18.  // 找到栈中第 1 个非零数字的位置，以此构建新的整数字符串
    19.  int offset = 0;
    20.  while (offset < newLength && stack[offset] == '0') {
    21.      offset++;
    22.  }
    23.  return offset == newLength ? "0" : new String(stack, offset, newLength - offset);
    24. }
    上述代码非常巧妙地运用了栈的特性，在遍历原整数的数字时，让所有数字一个一个入栈，当某个数字需要删除时，让该数字出栈。最后，程序把栈中的元素转化为字符串类型的结果。
    下面仍然以整数541270936，k =3 为例。
  • 当遍历到数字5时，数字5入栈。
  • 当遍历到数字4时，发现栈顶5＞4，栈顶5出栈，数字4入栈。
  • 当遍历到数字1时，发现栈顶4＞1，栈顶4出栈，数字1入栈。
  • 然后继续遍历数字2、数字7，并依次入栈。
  • 最后，遍历数字0，发现栈顶7＞0，栈顶7出栈，数字0入栈。
  • 此时k的次数已经用完，无须再比较，让剩下的数字一起入栈即可。

上面的方法只对所有数字遍历了一次，遍历的时间复杂度是O (n )，把栈转化为字符串的时间复杂度也是O (n )，所以最终的时间复杂度是贪心算法 - 图2 。