題目描述:給定代表非負整數的字串 num 和整數 k,從 num 中恰好刪除 k 個數字,使剩餘的數字(保持原相對順序)所代表的整數最小,回傳結果字串(不含前導零;若結果為空則回傳 "0")。
解題思路:
要讓剩餘數字最小,貪心策略是:若當前數字比前面的數字小,就應刪除前面那個更大的數字。這正好對應單調遞增棧的操作:
num 的每個數字 d,維護一個單調不遞減的棧 stk:
> d 且還有刪除配額(k > 0),則彈出棧頂並 k--。d 推入棧。k > 0(刪除次數未用完),從棧尾(最大端)刪除 k 個元素。'0'。"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,當沒有任何元素被彈出時)。
1. 初始化空棧 stk(用字串模擬)。
2. 遍歷 num 的每個字元 d:
a. 重複:若棧非空 且 棧頂 > d 且 k > 0,
則彈出棧頂,k 減 1。
b. 將 d 推入棧。
3. 若 k > 0,從棧尾移除 k 個元素。
4. 找到第一個非 '0' 的位置 start(保留最後一個 '0',避免全空)。
5. 若棧為空,回傳 "0";否則回傳 stk[start..end]。每次從字串中找第一個「下降點」(即 num[i] > num[i+1])並刪除 num[i],重複 k 次。若找不到下降點則刪除末尾字元。
時間複雜度:O(kn)|空間複雜度:O(n)
在 k 很大時效能差,但邏輯清晰,適合理解題意。
此題不適用優先佇列,因為刪除的數字必須保持相對順序,而優先佇列無法保證順序約束。這是單調棧解法的核心優勢所在。
一次遍歷,貪心彈出所有使結果變大的數字,O(n) 時間內完成。注意需處理三個邊界:k 未用完、前導零、空字串。
時間複雜度:O(n)|空間複雜度:O(n)
Remove Duplicate Letters(LeetCode 316):同樣使用單調遞增棧貪心,但限制改為每個字元只保留一個。思考兩題的彈出條件有何不同:316 用 inStack 控制,402 用 k 計數控制。
刪除後使結果最大:若改為刪除 k 個數字使結果最大,應如何修改?提示:將單調遞增棧改為單調遞減棧,彈出條件反向(棧頂 < 當前數字時彈出)。
Largest Number(LeetCode 179):給定一組整數,排列組合成最大數。此題思路不同(排序比較器),但同樣涉及貪心選擇數字順序,可作為進階練習。