Remove K Digits

Question

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.

LeetCodeleetcode.com/problems/remove-k-digits

Solution

/*
@param: String, int
@return: String
Algorithm: 用stack来存放char, 如果下一个char < stack.peek(),则pop();
直到k == 0，主要corner case: 首位不能为0，pop()之前要判断stack.isEmpty();
*/
public String removeKdigits(String num, int k) {
    if (k >= num.length()) return "0";
    
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < num.length(); i++) {
        char c = num.charAt(i);
        while (k > 0 && !stack.isEmpty() && c < stack.peek()) {
            stack.pop();
            k--;               
        }         
        stack.push(c);
    }
    while (k > 0) { stack.pop(); k--;}
    
    StringBuilder res = new StringBuilder();
    while (!stack.isEmpty()) res.append(stack.pop());
    res.reverse();
    while (res.charAt(0) == '0' && res.length() > 1) res.deleteCharAt(0);
    return res.toString();
}