【原】358，移掉K位数字

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

• num 的长度小于 10002 且 ≥ k。

• num 不会包含任何前导零。

示例 1 :

输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。

答案：

 1public String removeKdigits(String num, int k) {
 2    if (num.length() <= k)
 3        return "0";
 4    int digits = num.length() - k;
 5    char[] stk = new char[digits];
 6    int top = 0;
 7    for (int i = 0; i < num.length(); i++) {
 8        char c = num.charAt(i);
 9        while (top > 0 && stk[top - 1] > c && k > 0) {
10            k--;
11            top--;
12        }
13        if (top < digits) {
14            stk[top++] = c;
15        } else {
16            k--;
17        }
18    }
19    int idx = 0;
20    while (idx < digits && stk[idx] == '0')
21        idx++;
22    return idx == digits ? "0" : new String(stk, idx, digits - idx);
23}

解析：

我们可以先不用看上面的代码，等我们分析完之后再看，否则直接看容易懵。上面的题说的是从一个字符串num中移除k个数字，使剩下的数字最小。我们可以先从移除一个数字开始看

所以我们找出了一个规律就是，就是从左往右删除第一个降序开始的值。

比如第一个3156，31是降序，所以删除3；

比如第二个1563，63是降序，所以删除6；

比如第二个3756，75是降序，所以删除7。

如果没有降序的，比如1234，我们就删除最后一个，结果才能是最小。

我们再来举一个移除两个数字的例子

所以规律很容易发现了，就是从左往右删除开始降序的数字，直到删除k个为止。或者也可以这样理解，就是每遍历一个数字就要判断他前面有没有比他大的数字，如果有就删除，直到累计删除k个为止。

1，那么这时候问题就来了，如果遍历完了删除的还不到k个怎么办呢，就像上面说的1234没有降序的这种，我们就删除最后的几个数字，凑够k个为止。

2，这个时候还会有一个问题，比如2014，如果我们删除一个数字让剩下的数字最小，我们删除的是2，那么结果就会变成014，所以我们还要把前导0去掉。

所以原理就这么简单。再来看上面的代码是不是如醍醐灌顶般豁然开朗。

而上面的代码稍微有点不同的是，他没有在原始字符串上操作，而是使用了一个临时数组stk，他会把原始字符串逐个放到stk数组中，放的时候如果发现前面有比他大的，就把前面比他大的移除掉，第13行有个判断，如果个数达到了那么当前值就不在添加了，在下一轮的for循环中还会进行判断，第20行通过循环去掉前导0。