182. Delete Digits

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"

Thinking

rest = N-k

find teh 

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

1. 当stack不是空的时候
2. stack的top比现有的数大
3. 还未达到删除数
目的：选出倒序的k个最小数


然后需要一个temp stack 反转

如果没有达到k个数，res 的
ex： 12345 3
stack：1
rest：3-1

public class Solution {
    /*
     * @param A: A positive integer which has N digits, A is a string
     * @param l: Remove k digits
     * @return: A string
     */
    public String DeleteDigits(String A, int k) {
        // write your code here
        String res = "";
        if(A.length() == 0 || A == null) {
            return res;
        }
        
        Stack<Character> stack = new Stack<Character>();
        int count = 0;
        for(int i = 0; i < A.length(); i++) {
            char curt = A.charAt(i);
            
            // 
            // 1. 当stack不是空的时候
            // 2. stack的top比现有的数大
            // 3. 还未达到删除数
            // 尽可能选出倒序的k个最小数
            // 
            
            while(!stack.isEmpty() && stack.peek() > curt && count < k){
                stack.pop();
                count++;
            }
            stack.push(curt);
        }
        
        //反序stack
        Stack<Character> temp = new Stack<Character>();
        while(!stack.isEmpty()) {
            temp.push(stack.pop());
        }
        
        while(!temp.isEmpty()) {
            res = res + temp.pop();
        }
        
        // Case: count没有达到k个
        // ? 是不是直接substring k就行了
        if(count < k){
            int num = k - count;
            res = res.substring(0, res.length()-num); 
        }
        
        
        // Case: 最前面的0
        // count all the zeros in the result
        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;
        
    }
}


优化：
循环k次：
    删除[j] > [j+1]
删除前置0

StringBuilder sb = new StringBuilder(A);
        int i, j;

        for (i = 0; i < k; i++) {

            // 如果 [j] <= [j+1] 保留 并 j++
            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();