Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note: The length of num is less than 10002 and will be ≥ k. The given num does not contain any leading zero. Example 1:

Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest. Example 2:

Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes. Example 3:

Input: num = "10", k = 2 Output: "0" Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Solution

public class Solution {
    public String removeKdigits(String num, int k) {
        if(num == null || num.length() == 0 || k >= num.length()) return "0";
        int[] stack = new int[num.length()];
        int len = 0;

        int delNum = 0;
        for(int i = 0; i < num.length(); i++) {
            int val = num.charAt(i) - '0';
            if(len == 0 || val >= stack[len-1]) {
                // push 
                stack[len++] = val;
            } else {
                while(delNum < k && len > 0 && val < stack[len-1]) {
                    len--;
                    delNum++;
                }
                stack[len++] = val;
            }
        }

        // pick the first num.length() - k, numbers ignore zero
        int nonzero = -1;
        for(int i = 0; i < num.length() - k; i++) {
            if(stack[i] != 0) {
                nonzero = i;
                break;
            }
        }
        if(nonzero == -1) return "0";
        else {
            StringBuilder sb = new StringBuilder();
            for(int i = nonzero; i < num.length() - k; i++) {
                sb.append(stack[i]);
            }
            return sb.toString();
        }

    }
}