402. Remove K Digits

Remove K Digits

題目描述：給定代表非負整數的字串 num 和整數 k，從 num 中恰好刪除 k 個數字，使剩餘的數字（保持原相對順序）所代表的整數最小，回傳結果字串（不含前導零；若結果為空則回傳 "0"）。

解題思路：

要讓剩餘數字最小，貪心策略是：若當前數字比前面的數字小，就應刪除前面那個更大的數字。這正好對應單調遞增棧的操作：

1. 遍歷 num 的每個數字 d，維護一個單調不遞減的棧 stk：
   • 若棧頂元素 > d 且還有刪除配額（k > 0），則彈出棧頂並 k--。
   • 重複上述操作直到條件不滿足，再將 d 推入棧。
2. 遍歷結束後若 k > 0（刪除次數未用完），從棧尾（最大端）刪除 k 個元素。
3. 去除前導零：從棧的頭部跳過所有 '0'。
4. 若棧為空，回傳 "0"；否則回傳棧的內容。

以 num = "1432219", k = 3 為例：

• 遇 4：棧 [1, 4]
• 遇 3：4 > 3 → 彈出 4，k=2；棧 [1, 3]
• 遇 2：3 > 2 → 彈出 3，k=1；棧 [1, 2]
• 遇 2：2 == 2，不彈，棧 [1, 2, 2]
• 遇 1：2 > 1 → 彈出 2，k=0；棧 [1, 2, 1]（k=0 停止彈出）
• 繼續推入 9：棧 [1, 2, 1, 9]
• 結果："1219"

時間複雜度：O(n) — 每個數字最多被推入棧和彈出棧各一次，整體為線性時間（n 為 num 的長度）。

空間複雜度：O(n) — 棧最多儲存 n 個字元（即完整的 num，當沒有任何元素被彈出時）。

替代方法

方法一：暴力枚舉

每次從字串中找第一個「下降點」（即 num[i] > num[i+1]）並刪除 num[i]，重複 k 次。若找不到下降點則刪除末尾字元。

時間複雜度：O(kn)｜空間複雜度：O(n)

在 k 很大時效能差，但邏輯清晰，適合理解題意。

方法二：優先佇列（Priority Queue）

此題不適用優先佇列，因為刪除的數字必須保持相對順序，而優先佇列無法保證順序約束。這是單調棧解法的核心優勢所在。

方法三：單調棧（推薦，本題解法）

一次遍歷，貪心彈出所有使結果變大的數字，O(n) 時間內完成。注意需處理三個邊界：k 未用完、前導零、空字串。

時間複雜度：O(n)｜空間複雜度：O(n)

延伸問題

1. Remove Duplicate Letters（LeetCode 316）：同樣使用單調遞增棧貪心，但限制改為每個字元只保留一個。思考兩題的彈出條件有何不同：316 用 inStack 控制，402 用 k 計數控制。

2. 刪除後使結果最大：若改為刪除 k 個數字使結果最大，應如何修改？提示：將單調遞增棧改為單調遞減棧，彈出條件反向（棧頂 < 當前數字時彈出）。

3. Largest Number（LeetCode 179）：給定一組整數，排列組合成最大數。此題思路不同（排序比較器），但同樣涉及貪心選擇數字順序，可作為進階練習。