Delete Digits 182

Question

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.

Find the smallest integer after remove k digits.

N <= 240 and k <= N,

Example

Given an integer A = "178542", k = 4

return a string "12"

Solution

要让一个数尽量小，那么就要把小的数字尽量放到前面，如果前面有比它大的数字，那么就到把在它前面且比它大的数字都要删除掉，直到已经删掉k个数字，所以最后留下的是一个递增数列。同时要考虑一些特殊情况，比如前置0要去掉，以及如果遍历一遍之后发现删去的数不足k个，则删去最后的k－count个数。

代码如下：

public class Solution {
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    public String DeleteDigits(String A, int k) {
        // write your code here
        String res = "";
        if(A == null || A.length() == 0){
            return res;
        }
        //为了使得剩下的数最小，要尽可能地把高位的大的数删掉
        Stack<Character> stack = new Stack<Character>();
        int count = 0;
        for(int i = 0; i < A.length(); i++){
            char curt = A.charAt(i);
            while(!stack.isEmpty() && stack.peek() > curt && count < k){
                stack.pop();
                count++;
            }
            stack.push(curt);
        }

        Stack<Character> temp = new Stack<Character>();
        while(!stack.isEmpty()){
            temp.push(stack.pop());
        }
        while(!temp.isEmpty()){
            res = res + temp.pop();
        }

        //count < k case
        if(count < k){
            int num = k - count;
            res = res.substring(0, res.length() - num);
        }

        //front 0 case
        int i = 0;
        while(i < res.length() && res.charAt(i) == '0'){
            i++;
        }
        if(i == res.length()){
            res = "0";
        }else{
            res = res.substring(i);
        }

        return res;
    }
}

优化版本：

public class Solution {
    /**
     *@param A: A positive integer which has N digits, A is a string.
     *@param k: Remove k digits.
     *@return: A string
     */
    public String DeleteDigits(String A, int k) {
        // write your code here
         StringBuilder sb = new StringBuilder(A);
        int i, j;
        for (i = 0; i < k; i++) {
            for (j = 0; j < sb.length() - 1
                    && sb.charAt(j) <= sb.charAt(j + 1); j++) {
            }
            sb.delete(j, j + 1);
        }
        while (sb.length() > 1 && sb.charAt(0)=='0'){
            sb.delete(0,1);
        }
        return sb.toString();
    }
}