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, ExampleGiven an integer A = 178542, k = 4return a string "12"

第二遍做法：跟  和 很像

维护一个stack，每次把当前char加进去，直到加到A.length()-k个。加之前看看能不能删一些栈顶元素，条件：

1. 栈非空

2. 当前元素<栈顶元素

3. A后面剩的元素数目 >= A.length()-k-stack.size()

这样弄出来栈里面存着最后的数

注意可能以0开头，没关系，因为题目是删掉元素剩的最小的数，允许的，只用最后返回结果把开头0去掉就行

1 public class Solution { 2     /** 3      *@param A: A positive integer which has N digits, A is a string. 4      *@param k: Remove k digits. 5      *@return: A string 6      */ 7     public String DeleteDigits(String A, int k) { 8         // write your code here 9         if (k == 0) return A;10         if (A == null || A.length()==0 || A.length()==k) return "";11         Stack
     
       stack = new Stack
      
       ();12         int len = A.length()-k;13         for (int i=0; i
       
        =len-stack.size()) {16                 stack.pop();17             }18             if (stack.size() < len) stack.push(c);19         }20         StringBuffer res = new StringBuffer();21         while (!stack.isEmpty()) {22             res.insert(0, stack.pop());23         }24         while (res.length()>0 && res.charAt(0)=='0') {25             res.deleteCharAt(0);26         }27         return res.toString();28     }29 }
       
      
     

这道题跟Leetcode里面的那道很像，那个题要找比一个数大的下一个数，于是从这个数的右边开始，找第一个递减的位置所在。这道题也是类似，只不过从这个数的左边开始，找第一个递减的位置所在。那道题是想要改动的影响最小，所以从右边开始扫描。这道题是想要改动的影响最大，所以从左边开始扫描。

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

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

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

1 public class Solution { 2     /** 3      *@param A: A positive integer which has N digits, A is a string. 4      *@param k: Remove k digits. 5      *@return: A string 6      */ 7     public String DeleteDigits(String A, int k) { 8         Stack
     
       st = new Stack
      
       (); 9         int popCount = 0;10         StringBuffer res = new StringBuffer();11         for (int i=0; i
       
        = 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 }