題目描述:給定字串 s,刪除重複出現的字母,使每個字母恰好只出現一次,且回傳結果在所有可能的結果中字典序最小。
解題思路:
此題的關鍵在於:當我們遇到一個字元比棧頂字元還小時,若棧頂字元在後面還會再出現,我們可以貪心地將棧頂字元彈出(因為之後還能補回),換取更小的字典序結果。
使用一個單調遞增棧維護目前的答案:
last[c],以及維護 inStack[c] 布林陣列記錄字元是否已在棧中。c:
c 已在棧中,直接跳過(不重複加入)。top > c,且 last[top] > i(表示後面還有),就彈出棧頂並設 inStack[top] = false。c 推入棧,並設 inStack[c] = true。以 s = "bcabc" 為例:
b、c、a:遇到 a 時,c(後面還有)→ 彈出,b(後面還有)→ 彈出,推入 a。b、c:依序推入,最終棧為 [a, b, c],答案為 "abc"。時間複雜度:O(n) — 每個字元最多被推入棧和彈出棧各一次,因此整體遍歷為線性時間(n 為字串長度)。
空間複雜度:O(1) — last 和 inStack 陣列大小固定為 26(字母表大小),棧的大小最多也是 26,均視為常數空間(不含輸出)。
1. 初始化 last[26],遍歷 s,記錄每個字元最後出現的索引。
2. 初始化 inStack[26] 全為 false,初始化空棧 stk。
3. 遍歷 s 的每個字元 c(索引 i):
a. 若 inStack[c] 為 true,跳過(continue)。
b. 重複以下操作:若棧非空 且 棧頂 > c 且 last[棧頂] > i,
則彈出棧頂,並將 inStack[棧頂] 設為 false。
c. 將 c 推入棧,並設 inStack[c] = true。
4. 將棧的內容(由底到頂)組合成字串並回傳。對每個位置嘗試刪除一個重複字元,遞迴求最小字典序結果。時間複雜度為指數級,僅適用於非常短的字串,不實用。
時間複雜度:O(2ⁿ)|空間複雜度:O(n)
每次在前綴中找到第一個字典序最小且後面仍覆蓋所有字元的字元,作為結果的第一個字元,然後遞迴處理剩餘字串。邏輯等價於單調棧,但實作較複雜。
時間複雜度:O(26n)|空間複雜度:O(n)
以 inStack 避免重複,以 last 決定是否可彈出,一次遍歷完成。最簡潔高效。
時間複雜度:O(n)|空間複雜度:O(1)
LeetCode 1081 - Smallest Subsequence of Distinct Characters:此題與 316 完全相同,只是題目敘述不同,可作為練習驗證理解。
若允許字元重複出現 k 次:如果每個字元最多保留 k 次而非 1 次,演算法應如何修改?提示:inStack 改為計數陣列,彈出條件也需相應調整。
結合 Remove K Digits(LeetCode 402):兩題都使用單調遞增棧貪心,但 402 是刪除固定數量的數字。思考兩者的相同之處:何時彈出、何時停止,以及如何處理邊界條件(結尾多餘元素、前導零等)。