删除k个数字后的最小值

给定一个只包含数字的字符串，要求在原字符串基础上删除k个数字后，使新字符串的数字最小。

题目来源：LeetCode-402. Remove K Digits，原题目如下：

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

The length of num is less than 10002 and will be ≥ k.The given num does not contain any leading zero.

 先考虑只删除一个数字的情况，比如：1753，删除一个元素后最小的数字为：153；再如：6493，删除一个元素后最小的数为：493；再如，12345，删除一个元素后最小的数字为：1234。我们可以发现每次删除的数字是第一个开始递减的数字，如果一直递增就删除最后一个元素，如果删除k个元素，我们重复k次就好了。

AC代码;

class Solution { public String removeKdigits(String num, int k) { if(num.length() <= k) return "0"; int newLength = num.length() - k; char[] stack = new char[num.length()]; int cur = 0; for (int i = 0; i < num.length(); i++) { char c = num.charAt(i); while (cur > 0 && stack[cur - 1] > c && k > 0) { cur--; k--; } stack[cur++] = c; } int offset = 0; while (offset < newLength && stack[offset] == '0') { offset++; } return offset == newLength ? "0" : new String(stack, offset, newLength - offset); } }

上述代码是由一定的优化的！，基本的思路就是每次删除一个元素后，不再是从头开始遍历了。

好了，我们下期见！！