↓快轉到主要內容
  1. Leetcode/

[LeetCode] 402. Remove K Digits

·
LeetCode string monotonic stack
目錄

題目連結：402. Remove K Digits

解題思路
#

這一題一開始我想到 O(n^2) 的方法：

  1. 迭代 num 陣列，每次新增一個數字 n 進 list 中。
  2. 當 list 的長度大於 num.length-k 後，將 list 中的元素從頭到尾與剛剛新增的數字 n 進行比較，當找到第一個大於 n 的數字後將它 pop 掉，如果都沒有就把剛剛新增的 n pop 掉。
  3. 最後去除開頭為 '0' 的部分便是答案了。

但想當然的一定會 TLE（num.length 最大到 10^5）。

如果要在 O(n) 時間來解決這個問題，那便會需要用到單調隊列（monotonic stack）的概念。解決這題的核心在於：我們希望左邊的數字越小越好，因此可以透過維護一個遞增的單調隊列來完成，只要：

  1. k > 0（也就是還可以移除字元）。
  2. num[i-1] > num[i]，代表把 num[i-1] 刪除後以 num[i] 取代可以得到較小的數字。

那便可以把隊列頂部（最大）的數字 pop 出來以 num[i] 來取代。

但還要考慮一個情況： 如果整個 num 都跑過一遍了，這時如果 k > 0 是甚麼意思呢？這代表說不需要移除 k 個數字就可以做出一個遞增的單調隊列。但題目要求一定要移除 k 個數字呀！怎麼辦呢？ 如果移除最左邊的數字，那這樣得出來的結果就會變大（因為數字是遞增的，例如：“123” 想取兩位數，移除 “1” 的話會得到 “23”，但最小的結果是 “12”），所以從尾端開始移除數字直到隊列的長度等於 num.length-k 即可！

程式碼
#

C++
#

class Solution {
public:
    string removeKdigits(string num, int k) {
        string res;
        std::stack<int> stack;

        for (char c: num) {
            while (!stack.empty() && k > 0 && stack.top() > c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }

        while (k > 0) {
            stack.pop();
            k--;
        }

        while (!stack.empty()) {
            res += stack.top();
            stack.pop();
        }
        reverse(res.begin(), res.end());

        // remove leading 0
        size_t pos = res.find_first_not_of('0');
        if (pos != string::npos)
            res = res.substr(pos);
        else
            res = "0";

        return res;
    }
};

Python
#

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []

        for c in num:
            while stack and c < stack[-1] and k > 0:
                stack.pop()
                k -= 1
            stack.append(c)
        
        if k > 0:
            stack = stack[:-k]
        
        res = "".join(stack).lstrip("0")
        return res if res != "" else "0"