Delete Digits

 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         
 9         if (A == null || A.length() == 0 || k <= 0) return A;
10         if (A.length() == k) return "";
11         
12         StringBuilder sb = new StringBuilder();
13         sb.append(A.charAt(0));
14         
15         for (int p = 1; p < A.length(); p++) {
16             //这题关键的部分是如果当前这个数比前一个数小，我们就一定要把当前这个数替换掉前一个数。因为这样我们得到的数就一定更小。
17             // 但是也不是可以无限替换，我们得保证A后面部分的substring长度+当前sb的长度 >= A.length() - k
18             while (sb.length() >= 1 && A.charAt(p) < sb.charAt(sb.length() - 1) && sb.length() > p - k) {
19                 sb.deleteCharAt(sb.length() - 1);
20             }
21             if (sb.length() < A.length() - k) {
22                 sb.append(A.charAt(p));
23             }
24         }
25         int i = 0;
26         // remove the extra 0 at the beginning
27         while(sb.length() > 0 && sb.charAt(0) == ‘0‘) {
28             sb.deleteCharAt(0);
29         }
30         
31         return sb.toString() + "";
32     }
33 }