402. Remove K Digits.md

402. Remove K Digits

---

leetcode-cn Daily Challenge on November 15th, 2020.

---

Difficulty : Medium

Related Topics : Stack、Greedy

---

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

• mine
  • Java
    • Runtime: 8 ms, faster than 35.64%, Memory Usage: 39.5 MB, less than 43.60% of Java online submissions

      // O(N * K)time
      // O(N)space
      public String removeKdigits(String num, int k) {
          int n = num.length();
          if (k >= n) return "0";
          List<Character> arr = new ArrayList<>(n);
          for (char c : num.toCharArray()) arr.add(c);
          while (k > 0 && arr.size() > 0) {
              int d = 0;
              for (int i = 1; i < arr.size(); i++) {
                  if (arr.get(i) >= arr.get(i - 1)) d++;
                  else break;
              }
              arr.remove(d);
              while (arr.size() != 0 && arr.get(0) == '0') arr.remove(0);
              k--;
          }
          StringBuilder sb = new StringBuilder();
          for (char c : arr) {
              sb.append(c);
          }
          return sb.length() == 0 ? "0" : sb.toString();
      }
      

---

• the most votes

• Runtime: 2 ms, faster than 98.67%, Memory Usage: 38.7 MB, less than 94.96% of Java online submissions

  // O(N)time
  // O(N)space
  public String removeKdigits(String num, int k) {
      int digits = num.length() - k;
      char[] stk = new char[num.length()];
      int top = 0;
      // k keeps track of how many characters we can remove
      // if the previous character in stk is larger than the current one
      // then removing it will get a smaller number
      // but we can only do so when k is larger than 0
      for (int i = 0; i < num.length(); ++i) {
          char c = num.charAt(i);
          while (top > 0 && stk[top-1] > c && k > 0) {
              top -= 1;
              k -= 1;
          }
          stk[top++] = c;
      }
      // find the index of first non-zero digit
      int idx = 0;
      while (idx < digits && stk[idx] == '0') idx++;
      return idx == digits? "0": new String(stk, idx, digits - idx);
  }
  

---