2.7 Remove k digits

Description

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.

Method

Stack+ greedy

Time and Space Complexity

O(n) O(n)

Code

public class Solution {

  public String removeKdigits(String num, int k) {
       if (num == null || num.length() <= k){
           return "0";
       }
      Stack<Character> stack = new Stack<Character>();
      int len = num.length();
      StringBuilder sb = new StringBuilder();
      for (int i = 0; i < len; i++){
            if (stack.isEmpty() || num.charAt(i) >= stack.peek()){
                stack.push(num.charAt(i));
            } else {
                while (k > 0 && !stack.isEmpty() && num.charAt(i) < stack.peek()){
                      stack.pop();
                      k--;
                }
                stack.push(num.charAt(i));
            }
      }
      while (k > 0){
          stack.pop();
          k--;
      }
      while (!stack.isEmpty()){
          sb.insert(0,stack.pop());
      }
      String res = sb.toString();
      //System.out.println(res);
      int i = 0;
      for (; i < res.length(); i++){
            if (res.charAt(i) != '0'){
                break;
            }
      }
      return i == res.length() ? "0" : res.substring(i);

}

}