402. Remove K Digits

題目連結: 402. Remove K Digits

題目描述

給定一個表示非負整數的字串 num，從中移除 k 個數字，使得剩下的數字組成的數值最小。

注意：

• num 不可以有前導零，除非結果是 0 本身。

限制條件

• 1 <= k <= num.length <= 10^5
• num 只包含數字字符。
• num 除了數字 0 本身外，不會有其他前導零。

解題思路

為了在移除 k 個數字後使得數值最小，我們需要盡可能移除較大的數字，特別是靠前位置的較大數字。這可以使用單調堆疊（Monotonic Stack）來實現。

具體步驟

1. 初始化：建立一個空的字串 stack，用於模擬單調遞增的堆疊。
2. 遍歷字串 num：
   • 對於字串中的每個字符 digit：
     • 當前字符比堆疊頂端元素小，且還可以移除數字時（k > 0），就彈出堆疊頂端元素，k--。
     • 將當前字符壓入堆疊中。
3. 處理剩餘的 k：
   • 如果在遍歷完 num 後，k 仍大於 0，則從堆疊頂端開始彈出元素，直到 k == 0。
4. 去除前導零：
   • 從堆疊的左側開始，移除所有的前導零。
5. 構造結果：
   • 將堆疊中的字符組合成字串。
   • 如果結果為空，則返回 "0"。

程式碼

class Solution {
public:
    string removeKdigits(string num, int k) {
        const int n = num.size();
        string s = "";
        for (int i = 0; i < n; i += 1) {
            while (k > 0 && !s.empty() && s.back() > num[i]) {
                s.pop_back();
                k -= 1;
            }

            s.push_back(num[i]);

            if (s.size() == 1 && s.back() == '0') {
                s.pop_back();
            }
        }

        while (k > 0 && !s.empty()) {
            s.pop_back();
            k -= 1;
        }

        return s.empty() ? "0" : s;
    }
};

時間與空間複雜度分析

• 時間複雜度：O(n)，其中 n 是字串 num 的長度。
  • 分析：每個數字最多只會進入和彈出堆疊一次，因此總的操作次數與 n 成正比。
• 空間複雜度：O(n)，用於存儲堆疊 stack。
  • 分析：最壞情況下，堆疊中會存儲所有的字符。