https://www.lintcode.com/problem/remove-k-digits/description
给定一个非负整数，以字符串 s s s形式给出，允许从中删去 k k k个字符，问能得到的最小整数是多少，也以字符串形式返回。规定如果 k k k超过了 s s s长度则返回 0 0 0。返回的字符串要去掉前导 0 0 0。
思路是单调栈（贪心）。显然如果 k ≥ l s k\ge l_s k≥ls，那说明可以删光，直接返回 0 0 0即可。否则遍历 s s s，并维护一个栈，一旦遇到栈顶大于 s [ i ] s[i] s[i]的情形，我们就删掉栈顶，直到小于等于的时候再将 s [ i ] s[i] s[i]入栈。如果删不够 k k k个，那就把末尾的数字再删掉些即可。接着再去掉前导 0 0 0即可。算法证明如下： 首先，如果只允许删一个数字，那么显然上述做法是正确的，可以得到最小值。接着考虑 k > 1 k > 1 k>1的情况。只需要证明一个很简单的结论即可，即如果两个字符串 s 1 s_1 s1和 s 2 s_2 s2，有 ∀ i , s 1 [ i ] ≥ s 2 [ i ] \forall i, s_1[i]\ge s_2[i] ∀i,s1[i]≥s2[i]，那么这两个字符串得到的最小数一定也有 s 1 ′ ≥ s 2 ′ s_1'\ge s_2' s1′≥s2′。对于任意一种对 s 1 s_1 s1的操作，我们apply相同的操作在 s 2 s_2 s2上，操作完显然 s 1 s_1 s1的结果一定大于等于 s 2 s_2 s2的结果，当然对于 s 1 s_1 s1的最优解的操作一样成立，所以结论正确。证明完这个结论之后，接下来数学归纳法，对 s s s长度进行归纳。如果某个最优解删除的数字与贪心法删除的不一样，那么就找从左向右数第一个不一样的地方，删完之后贪心法得到的数字是更优的（严格来讲是“不会更差”，不一定就“更优”），接下来继续删的时候由归纳假设，贪心法是最优的，再由上面的结论知道，最后得到的数字一定小于等于最优解得到的数字，所以算法正确。
代码如下：
public class Solution { /** * @param num: a string * @param k: an integer * @return: return a string */ public String removeKdigits(String num, int k) { // write your code here if (k >= num.length()) { return "0"; } StringBuilder sb = new StringBuilder(); for (int i = 0; i < num.length(); i++) { while (sb.length() > 0 && sb.charAt(sb.length() - 1) > num.charAt(i) && k > 0) { sb.setLength(sb.length() - 1); k--; } sb.append(num.charAt(i)); } // 删掉末尾的k个数字 sb.setLength(sb.length() - k); // 去掉前导0 int i = 0; while (i + 1 < sb.length() && sb.charAt(i) == '0') { i++; } return sb.substring(i); } }时空复杂度 O ( l s ) O(l_s) O(ls)。
