Lintcode: Delete Digits - neverlandly - 博客园

Lintcode: Delete Digits - neverlandly - 博客园
Given string A representative a positive integer which has N digits, remove any k digits of the number, the remaining digits are arranged according to the original order to become a new positive integer. Make this new positive integers as small as possible. N <= 240 and k <=N, Example Given an integer A = 178542, k = 4 return a string "12"
https://codesolutiony.wordpress.com/2015/03/27/lintcode-delete-digits/
http://www.cnblogs.com/EdwardLiu/p/4276260.html
这道题跟Leetcode里面的那道Next Permutation很像，那个题要找比一个数大的下一个数，于是从这个数的右边开始，找第一个递减的位置所在。这道题也是类似，只不过从这个数的左边开始，找第一个递减的位置所在。那道题是想要改动的影响最小，所以从右边开始扫描。这道题是想要改动的影响最大，所以从左边开始扫描。

这道题，删掉一个数，相当于用这个数后面的数代替这个数。所以后面这个数一定要比当前小才行。所以找的是第一个递减的位置，把大的那个数删了。

这样做一次就是找到了：删除哪一个数，使得剩下的数最小。对剩下的数再做k次，就可以找到删除哪k个数，使得剩下的数最小。这其实是一个Greedy算法，因为这样每做一次，得到的都是当前最优的结果。

看起来需要O(Nk)时间复杂度，但其实用一个Stack，再记录pop了几次，O(2N)就好了

   public String DeleteDigits(String A, int k) {
 8         Stack<Integer> st = new Stack<Integer>();
 9         int popCount = 0;
10         StringBuffer res = new StringBuffer();
11         for (int i=0; i<A.length(); i++) {
12             int num = (int)(A.charAt(i) - '0');
13             if (st.isEmpty()) st.push(num);
14             else if (num >= st.peek()) {
15                 st.push(num);
16             }
17             else {
18                 if (popCount < k) {
19                     st.pop();
20                     i--;
21                     popCount++;
22                 }
23                 else {
24                     st.push(num);
25                 }
26             }
27         }
28         while (popCount < k) {
29             st.pop();
30             popCount++;
31         }
32         while (!st.isEmpty()) {
33             res.insert(0, st.pop());
34         }
35         while (res.length() > 1 && res.charAt(0) == '0') {
36             res.deleteCharAt(0);
37         }
38         return res.toString();
39     }
40 }

Read full article from Lintcode: Delete Digits - neverlandly - 博客园