402. Remove K Digits - Medium

前往題目

想法

• Stack

思路

Monotonic Stack，由小到大

1. 疊代整個string
2. 遇到當前數字比前一個小就彈出上一個數字(最多彈出k個)
3. 還有k剩餘就彈出最後面的數字
4. 回傳結果

要想到monotonic stack是這題的解法還真的有難度

Code

class Solution {
    public String removeKdigits(String num, int k) {
        Stack<Character> stack = new Stack();

        // Go through the string
        for (char c : num.toCharArray()) {
            // When current number is smaller than the top of the stack
            // We want a monotonic stack
            while (k > 0 && !stack.isEmpty() && c < stack.peek()) {
                // Remove the number
                --k;
                stack.pop();
            }
            stack.push(c);
        }

        // In case it is monotonic already
        while (k > 0 && !stack.isEmpty()) {
            --k;
            stack.pop();
        }

        StringBuilder res = new StringBuilder();

        // Assemble the result
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
        }

        // Remove leading zeros
        while (res.length() > 0 && res.charAt(0) == '0') {
            res.deleteCharAt(0);
        }
        
        // Handle edge case where result might be empty
        return res.length() > 0 ? res.toString() : "0";
    }
}