leetcode all in one，LeetCode Remove K Digits

原題鏈接在這里：https://leetcode.com/problems/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.?

leetcode all in one，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.

題解：

利用stack 保存從頭到尾iterate input num string的char, 若當前char 比stack頂小就一直pop棧頂直到 去掉的數等于k了或者棧頂的元素更小.

leetCode，然后從頭到尾找到第一個非0的位置 往后掃剩余digit長度的char.?

掃過的0也應該count在剩余digit長度中，只不過不會顯示在結果string里.

Time Complexity: O(n). n = num.length().

Space: O(n).

AC Java:

class Solution {
    public String removeKdigits(String num, int k) {
        if(num == null || num.length() == 0){
            return num;
        }
        
        int len = num.length();
        int remainDigits = len-k;
        char [] stk = new char[len];
        int top = 0;
        for(int i = 0; i<len; i++){
            char c = num.charAt(i);
            while(top>0 && c<stk[top-1] && k>0){
                top--;
                k--;
            }
            
            stk[top++] = c;
        }
        
        // 找到第一個不為0的index
        int ind = 0;
        while(ind<remainDigits && stk[ind]=='0'){
            ind++;
        }
        return ind == remainDigits ? "0" : new String(stk, ind, remainDigits-ind);
    }
}

leetcode中文、類似Create Maximum Number.