刷算法題最怕的一種狀態(tài)就是看題覺得很簡單一提交發(fā)現(xiàn)全是邊界問題。今天的訓(xùn)練營打卡內(nèi)容就是典型20. 有效的括號 和 1047. 刪除字符串中的所有相鄰重復(fù)項兩道題都屬于“字符串處理 ?！钡娜腴T組合代碼量都不大但幾乎每個訓(xùn)練營群里都會有人翻車。我這次把兩道題連在一起刷最大的收獲是抓住了它們共用的一個思考方式——用棧做“回退”。這篇文章會把解題過程、易錯點(diǎn)、以及我自己總結(jié)的棧題套路完整過一遍也希望給正在刷算法題的朋友一點(diǎn)參考。如果你剛開始學(xué)數(shù)據(jù)結(jié)構(gòu)棧這個概念可能很抽象。但這兩道題恰恰能把棧講明白一個講“匹配”一個講“消除”本質(zhì)上都依賴“后進(jìn)先出”這個特性。題目本身不算難難的是從“看著簡單”到“一次寫對”之間那段路而這正是訓(xùn)練營里最值得復(fù)盤的部分。1. 為什么“?！笔沁@兩道題共同的主角1.1 從處理順序看本質(zhì)先別急著寫代碼想一個問題有效的括號里最內(nèi)層的括號一定是最先被匹配的。比如{[]}雖然左花括號{最早出現(xiàn)但它要等到最后的}才匹配而中間的[和]反而先配對。這種“后進(jìn)先出”的順序和棧完全一致。1047 題也一樣。刪除相鄰重復(fù)項時假設(shè)字符串是abbac你先看到a然后看到兩個b消掉bb之后新的末尾變成了a結(jié)果下一個a又和它重復(fù)繼續(xù)消。你發(fā)現(xiàn)沒有——每次消除后需要回頭重新比較的永遠(yuǎn)是“最近還沒被處理掉的那個字符”。這個“最近的一個”恰恰就是棧頂。所以這兩道題雖然名字不同一個講括號合法性一個講字符串去重但骨子里是同一個模型我都會用一個容器把暫時沒法決定去留的元素緩存起來等新元素出現(xiàn)時優(yōu)先跟最近緩存的元素比一比。1.2 一個“回頭看”的判斷標(biāo)準(zhǔn)我自己刷題有個習(xí)慣看到一個新題目先不翻題解而是問三個問題處理當(dāng)前元素時需不需要知道上一個還沒處理完的元素如果上一個元素暫時不能決定去留能不能先存起來后面某一步會不會反過來用到這個“最近”的元素只要這三個問題里大多是“是”那這道題八成要用棧。拿 20 題舉例遇到一個右括號時你要判斷它能不能閉合最近的左括號如果最近那個左括號不匹配整個字符串就無效。這完全符合“回頭看”的定義。1047 題就更直接了當(dāng)前字符就是要跟上一個還沒被消除的字符比比完要么壓棧要么彈棧。這也是為什么我不建議死記“棧適合解決括號匹配”“棧適合解決表達(dá)式求值”這種結(jié)論。結(jié)論記多了題目稍微變形就懵了。記住“是否依賴最近未處理元素”這個判斷標(biāo)準(zhǔn)比記住十道題都管用。1.3 隊列為什么不能直接替代有一點(diǎn)值得拎出來說清楚為什么這兩道題不用隊列既然訓(xùn)練營標(biāo)題是“棧與隊列”很多初學(xué)者會想隊列不也能存元素嗎關(guān)鍵區(qū)別在比較對象。隊列是先進(jìn)先出隊頭是最早進(jìn)來的元素而這兩道題每次都比較“最近的元素”。如果你用隊列彈出的永遠(yuǎn)是老早以前進(jìn)來的字符完全對不上。比如括號匹配時出現(xiàn)右括號}時你需要看的是最近一個未匹配的左括號而不是最先出現(xiàn)的那個左括號。這是棧的天然主場。隊列當(dāng)然也有自己的人生比如 BFS 遍歷、滑動窗口、消息隊列削峰那些場景強(qiáng)調(diào)“先來先處理”。棧和隊列不是同一個工具服務(wù)的是兩種相反的需求。先把這兩道題吃透后面再對比隊列時你會非常清楚“為什么不能用棧實現(xiàn)一個排隊系統(tǒng)”。2. 20. 有效的括號一份匹配清單的三種典型錯法2.1 先弄清楚什么才叫“有效”題目給的是只有()[]{}的字符串要判斷括號是否有效。有效條件其實就兩條左括號必須被同類型的右括號閉合左括號必須以正確的順序閉合。第二條最容易忽略。([)]這種字符串每個括號類型都有左右數(shù)量也對但順序是錯的因為[先于(出現(xiàn)卻要在(之前閉合這就是交叉嵌套無效。我把這種字符串當(dāng)面試時的必考題因為它專門用來拆穿“只數(shù)個數(shù)不看順序”的寫法。還有幾個邊界想清楚空字符串返回 true只有左括號比如((false只有右括號比如]]false長度是奇數(shù)直接 false因為括號一定是成對的。2.2 三種典型錯法你多半中過招先說第一種三個計數(shù)器。有人用count1、count2、count3分別記錄三種括號遇到左加一遇到右減一最后檢查是否全為 0。這個寫法對()[]{}有效但對([)]完全失效因為計數(shù)器永遠(yuǎn)不會出現(xiàn)負(fù)數(shù)最后也是 0可字符串是無效的。原因就是計數(shù)器丟了“順序”信息。第二種遇到右括號直接彈棧但不檢查棧空。比如字符串)或())第一個字符就是右括號此時棧還是空的你直接st.pop()就崩了或者訪問棧頂報錯。即使語言里不報錯邏輯上也必須判 false因為沒有任何左括號能跟這個右括號匹配。所以記住訪問棧頂或彈出之前永遠(yuǎn)先問一句“?？樟藛帷?。第三種循環(huán)結(jié)束后忘記檢查棧是否為空。比如(()遍歷完所有字符后棧里還剩下一個(說明這個左括號沒有被閉合當(dāng)然是 false。很多人寫代碼時注意力全放在循環(huán)里覺得循環(huán)跑完就完事了結(jié)果在最后一步栽跟頭。2.3 一種更不容易寫錯的寫法壓入“期待值”常見的思路是遇到左括號就壓入左括號遇到右括號再拿它跟棧頂比較。這種做法沒問題但需要維護(hù)一個映射表代碼會多一些。我更喜歡另一個寫法遇到左括號時直接壓入它對應(yīng)的右括號。比如遇到(壓入)遇到[壓入]遇到{壓入}。這樣等到遇到右括號時只需要做一件事檢查棧頂是不是當(dāng)前這個字符。是就彈出不是就返回 false。這個寫法的好處有兩個。第一少寫一層 map 查詢字符直接跟字符比較邏輯更直白。第二判斷條件集中在一個方向遇到右括號時?？照f明沒有可匹配的左括號棧頂不相等說明類型不匹配或順序錯誤。我個人在實際刷題中比較推薦這種套路尤其在白板面試時代碼短思路清楚。2.4 完整代碼和復(fù)雜度分析C 版本我用 std::stackbool isValid(string s) { if (s.size() % 2 1) return false; stackchar st; for (char c : s) { if (c () { st.push()); } else if (c [) { st.push(]); } else if (c {) { st.push(}); } else { if (st.empty() || st.top() ! c) { return false; } st.pop(); } } return st.empty(); }Python 版本可以用 list 模擬def isValid(s: str) - bool: if len(s) % 2 1: return False stack [] for ch in s: if ch (: stack.append()) elif ch [: stack.append(]) elif ch {: stack.append(}) else: if not stack or stack[-1] ! ch: return False stack.pop() return not stack時間復(fù)雜度 O(n)每個字符最多入棧一次、出棧一次?？臻g復(fù)雜度 O(n)最壞情況是字符串全是左括號比如((((((所有字符全壓進(jìn)棧里。這里可以加一個小優(yōu)化如果字符串長度是奇數(shù)直接返回 false連遍歷都不用。雖然理論上復(fù)雜度還是 O(n)但能省掉一半跑到最后的開銷。3. 1047. 刪除字符串中的所有相鄰重復(fù)項把“消消樂”寫進(jìn)循環(huán)3.1 為什么暴力替換的做法不可行先看一個經(jīng)典例子abba。直觀上先刪掉相鄰的bb剩下aa這兩個又相鄰重復(fù)得繼續(xù)刪最后結(jié)果是空串。如果你用常規(guī)的循環(huán) replace比如while (aa in s or bb in s ...)會面臨兩個問題。第一你可能只替換一次就退出循環(huán)漏掉了刪除后產(chǎn)生的新重復(fù)結(jié)果返回aa判錯。第二每次 replace 都要重新掃描整個字符串如果有連續(xù)觸發(fā)連鎖消除最壞復(fù)雜度會變成 O(n2)在字符串很長時就很難受了。這個例子正好暴露了問題的本質(zhì)刪除一對相鄰重復(fù)之后新暴露出來的字符可能又和更前面的字符重復(fù)所以需要一種機(jī)制能回到“前一個字符”繼續(xù)比較。這已經(jīng)明明白白告訴你要用棧。3.2 核心過程掃描、比較、彈出、回退我用abbaca完整走一遍題目要求的輸出是ca讀入a?？罩苯訅喝霔閇a]讀入b棧頂是a不相等壓入棧為[a, b]讀入b棧頂是b相等彈出棧為[a]讀入a棧頂是a相等彈出棧為[]讀入c棧空壓入棧為[c]讀入a棧頂是c不相等壓入棧為[c, a]。最后把棧里的字符拼起來得到ca。注意第三步到第四步的過程彈出的瞬間相當(dāng)于把剛才存入的那個b撤銷了隨后新讀入的a自動跟更早的a比較。這個“撤銷后再比較”的動作就是棧題里最迷人的地方。它看起來像是回頭走了一步但棧幫你把這個回頭動作做成了 O(1) 的常數(shù)時間操作。3.3 三種實現(xiàn)方式從樸素到優(yōu)化第一種Python 的 list 模擬棧def removeDuplicates(s: str) - str: stack [] for ch in s: if stack and stack[-1] ch: stack.pop() else: stack.append(ch) return .join(stack)這個寫法最簡單邏輯一目了然適合作為第一版答案。第二種C 直接用 string 當(dāng)作棧。因為 string 本身就支持push_back、pop_back、back這些操作天然就是 char 類型的棧string removeDuplicates(string s) { string result; for (char c : s) { if (!result.empty() result.back() c) { result.pop_back(); } else { result.push_back(c); } } return result; }這個做法有個額外好處最后返回的就是棧本身不需要再做一次拼接。第三種原地雙指針優(yōu)化。既然棧里的內(nèi)容就是結(jié)果字符串而且題目允許修改原字符串那么可以用一個 write 指針模擬棧的大小把原數(shù)組當(dāng)成?？臻g。掃描時如果當(dāng)前字符和s[write-1]相等說明棧頂和當(dāng)前字符重復(fù)write--表示彈出否則把當(dāng)前字符寫到s[write]位置然后write。最后把字符串截斷到 write 長度string removeDuplicates(string s) { int write 0; for (char c : s) { if (write 0 s[write - 1] c) { write--; } else { s[write] c; } } s.resize(write); return s; }這個版本空間復(fù)雜度為 O(1)只用了幾個整型變量不額外開辟?？臻g。它本質(zhì)上是“用數(shù)組手寫了一個?！薄Ｎ医ㄗh你先把樸素寫法搞懂再來看這個優(yōu)化不要一上來就用地板優(yōu)化否則容易看不懂。3.4 時間空間與調(diào)試心得時間復(fù)雜度 O(n)空間復(fù)雜度根據(jù)實現(xiàn)方式不同樸素版 O(n)雙指針版 O(1)。這塊我吃過一次虧說說調(diào)試心得。剛開始寫的時候我習(xí)慣在循環(huán)里打印當(dāng)前字符和棧頂?shù)枰⒁獾氖遣荒苤欢⒅跋嗟染蛷棾觥边@個分支。真正容易出問題的是“?？諘r”的情況如果棧是空的訪問stack[-1]會越界所以在判斷時一定要把stack非空放在前面寫成if stack and stack[-1] chPython 里順序不能反C 里同樣要先判斷!result.empty()。很多人一上來就寫if (result.back() ch)遇到空棧就去訪問直接崩掉。還有一個細(xì)節(jié)是大小寫敏感性。題目里沒說忽略大小寫所以A和a不算重復(fù)。刷題時別自己給題目加條件這屬于讀題不仔細(xì)的鍋。4. 兩道題一起刷我總結(jié)出的棧題解題模板4.1 四步拆題法把這兩道題放在一起復(fù)盤我提取出一個可復(fù)用的思考流程暫時叫它“四步拆題法”。第一步判斷場景處理當(dāng)前元素時需不需要跟“之前出現(xiàn)過的最近元素”做比較需要就往棧上想。第二步確定棧的語義棧里存什么20 題存的是“期待的右括號”也可以存左括號1047 題存的是“還沒被消除的字符”。語義不同代碼結(jié)構(gòu)完全不同。有些題存索引有些題存數(shù)值還有些題存計數(shù)器。第三步寫清入棧出棧條件什么時候壓入什么時候彈出這一步是代碼核心盡量寫成條件分支別混在同一個 if 里。第四步想結(jié)果怎么還原棧最后是中間結(jié)果怎么變成真正的答案20 題要求返回布爾值直接看?？詹豢?047 題要返回字符串需要把棧拼起來或者直接用 string 當(dāng)棧連拼接都省了。我把兩道題整理成一張對照表題目棧里存什么入棧條件出棧條件結(jié)果20.有效的括號期待的右括號遇到左括號棧頂?shù)扔诋?dāng)前右括號最后?？談t true1047.刪除相鄰重復(fù)未消除的字符當(dāng)前字符不等于棧頂當(dāng)前字符等于棧頂剩余棧元素拼接這樣一比較你會發(fā)現(xiàn)兩道題的本質(zhì)非常接近都是當(dāng)前元素和棧頂比較相等就走“消除/匹配”路線不相等就走“入棧”路線。只是 20 題需要額外處理“三種類型括號”的映射關(guān)系。4.2 判空是棧題的命門刷了這么多棧題我最想強(qiáng)調(diào)的一點(diǎn)是判空。幾乎所有棧相關(guān)的 bug都是從“訪問了不存在的棧頂”開始的。我見過太多類似的代碼遇到右括號直接st.pop()忘了先檢查st.empty()看到棧不為空但忘記循環(huán)結(jié)束后還要檢查或者在棧頂比較時不判斷棧是否為空導(dǎo)致 undefined behavior。這類問題在 LeetCode 上不一定每次都崩因為語言和編譯器不同表現(xiàn)也不太一樣但邏輯一定是錯的。我給自己定了一條規(guī)則寫任何棧題凡是涉及top、pop、back的操作先寫判空。哪怕這題不可能出現(xiàn)空棧訪問也要保留判斷因為代碼的可讀性和防御性比少寫一行更重要。面試時這個習(xí)慣非常加分它說明你考慮過邊界。4.3 用數(shù)組或字符串代替標(biāo)準(zhǔn)棧的實用技巧一開始刷題時我默認(rèn)用語言自帶的 stack 類后來發(fā)現(xiàn)不少場景里用數(shù)組或字符串模擬棧更順手。先說 C。std::stack 是一個容器適配器默認(rèn)底層是 std::deque操作上有push、pop、top。但如果你最終要按順序輸出棧內(nèi)元素stack 的遍歷并不方便得先把元素倒騰到另一個容器里。相反用 vector 或 string 模擬棧既能當(dāng)棧用又保留了順序訪問的能力。1047 題直接返回 string 當(dāng)棧就是這種思路的極致體現(xiàn)。Python 里同理list 本身就是最好的棧append 和 pop 都是 O(1)還能直接遍歷。很多從 Java 轉(zhuǎn)過來的人習(xí)慣去 import Stack 類其實沒必要。Java 官方也不推薦再用 Stack 類更建議用 ArrayDeque。語言細(xì)節(jié)因環(huán)境而異但核心思想一樣普通棧操作用動態(tài)數(shù)組模擬效率高、可控性好。當(dāng)然如果元素類型比較復(fù)雜比如需要存(字符, 出現(xiàn)次數(shù))這種 pair直接用一個 stackpairchar, int 或者 vectorpairint, int 都可以。只要你能保證壓入和彈出的順序符合“最近優(yōu)先”用什么容器反而不重要。5. 進(jìn)階一擊這兩道題的常見變形5.1 從“有效的括號”出發(fā)的三條升級路線20 題后面通常接著三道題難度逐步上升我建議按這個順序刷。第一道是 22. 生成括號。它要求生成所有有效的括號組合思路是回溯在遞歸過程中維護(hù)一個“當(dāng)前已生成的括號串”。判斷某個狀態(tài)是否合法時可以沿用 20 題的計數(shù)思路右括號數(shù)量不能超過左括號數(shù)量左括號數(shù)量不能超過 n。這道題用棧也能解但回溯 剪枝更主流它讓你明白括號合法性的另一種表達(dá)方式。第二道是 32. 最長有效括號。這道題難度明顯上來了常見的做法是棧里存索引而不是存字符。棧里先放一個-1作為基準(zhǔn)遇到左括號入棧遇到右括號彈棧再用當(dāng)前索引減去新的棧頂索引得到目前為止連續(xù)有效的長度。為什么不直接存括號字符因為你需要用索引來計算長度。這就是“棧的語義”變化帶來的思維挑戰(zhàn)也是 20 題之后很值得做的一道延伸。第三道是 678. 有效的括號字符串。它引入了一個通配符*可以當(dāng)左括號、右括號或者空字符。經(jīng)典做法是雙?；蛘邇蓚€計數(shù)器一個棧存左括號位置一個棧存星號位置最后統(tǒng)一配對。這個玩法已經(jīng)遠(yuǎn)超 20 題基礎(chǔ)范圍了但能讓你徹底理解“括號匹配”的多種條件。另外還有 71. 簡化路徑也屬于括號題之外的“棧模擬”延伸題本質(zhì)是用棧來處理路徑片段和..回退。刷完 20 題后直接做這道會有一種熟悉感。5.2 從“刪除相鄰重復(fù)”出發(fā)的同類題目1047 題也有一個教科書級別的擴(kuò)展就是 1209. 刪除字符串中的所有相鄰重復(fù)項 II。區(qū)別在于原始題是刪除相鄰的兩個相同字符而這道題要求刪除相鄰的 k 個相同字符。解法幾乎就是把 1047 的思路稍微升級棧里存的不是單個字符而是一個包含字符和連續(xù)次數(shù)的結(jié)構(gòu)。每新來一個字符如果和棧頂字符相同就把棧頂?shù)拇螖?shù)加一當(dāng)次數(shù)達(dá)到 k 時彈出棧頂。如果不同就壓入一個新的節(jié)點(diǎn)次數(shù)從 1 開始計。我給一個簡單的 Python 版本def removeDuplicates(s: str, k: int) - str: stack [] for ch in s: if stack and stack[-1][0] ch: stack[-1][1] 1 if stack[-1][1] k: stack.pop() else: stack.append([ch, 1]) return .join(ch * count for ch, count in stack)這個變形題的識別信號很清晰從“刪相鄰兩個”變成“刪相鄰 k 個”本質(zhì)上就是要你額外維護(hù)一個計數(shù)。只要你理解 1047 的“棧頂比較 彈出”模式1209 也只是一層窗戶紙。5.3 棧題的共同識別信號刷多了以后我對哪些題適合用棧有了條件反射。描述里如果出現(xiàn)“相鄰”“最近”“回退”“成對出現(xiàn)”“閉合順序”大概率跟棧有關(guān)。現(xiàn)實生活里的例子也很好記編輯器撤銷是棧瀏覽器后退按鈕是棧函數(shù)調(diào)用時的棧幀也是棧。你寫遞歸時系統(tǒng)編譯器就在背后維護(hù)一個調(diào)用棧。所以在做題時如果題目要求你模擬“撤銷”或“回滾”行為先想想能不能用棧表達(dá)。這種識別信號比刷題數(shù)量的價值更大因為它能幫你在面對新題時快速定位數(shù)據(jù)結(jié)構(gòu)方向。6. 和隊列一起看什么時候該換工具6.1 隊列的經(jīng)典“排隊”場景雖然今天這兩道題都是棧的主場但訓(xùn)練營標(biāo)題既然寫了“棧與隊列”還是值得把隊列一起拉出來看。隊列這種先進(jìn)先出的結(jié)構(gòu)適合處理“按順序、先到先處理”的問題。最常見的算法場景就是 BFS 廣度優(yōu)先搜索從起點(diǎn)開始先把第一層鄰居入隊再逐層向外擴(kuò)展每一層都必須按入隊順序處理這時候棧就不合適了。類似的還有滑動窗口最大值那題用的是“單調(diào)隊列”在窗口中維護(hù)一個有序隊列讓隊頭始終是最大值。在工程上消息隊列也是隊列思想的體現(xiàn)。生產(chǎn)者和消費(fèi)者解耦數(shù)據(jù)先放到隊列里再由消費(fèi)方按順序處理。面試系統(tǒng)設(shè)計時經(jīng)常會聊到 kafka、rabbitmq、rocketmq 的選型核心關(guān)注點(diǎn)就在順序性、可靠性和吞吐量。這跟咱們刷題時學(xué)的“先進(jìn)先出”是一脈相承的只是落到了分布式系統(tǒng)里。6.2 棧和隊列怎么快速做選擇我總結(jié)了一個簡單判斷法新元素需要和誰比較誰先被處理決定了用棧還是隊列。新元素要和“最近”的元素比較后到的先觸發(fā)處理邏輯用棧新元素要和“最早”的元素比較或必須嚴(yán)格按到達(dá)順序處理用隊列。舉幾個例子括號匹配是跟最近的左括號比用棧打印任務(wù)排隊是老的先打用隊列函數(shù)調(diào)用返回時后調(diào)用的函數(shù)先返回用棧。這個判斷法基本能覆蓋九成以上的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)題。6.3 一個容易忽略的點(diǎn)棧題也能嵌套隊列思維棧和隊列并非水火不容。有些題表面是棧實際卻要結(jié)合別的數(shù)據(jù)結(jié)構(gòu)。比如最小棧題要求設(shè)計一個棧能在 O(1) 時間內(nèi)拿到底部的最小值。經(jīng)典做法是用兩個棧一個正常存數(shù)據(jù)另一個只存“當(dāng)前出現(xiàn)過的最小值”每次 push 或 pop 時同步更新。這里底層思想是“單調(diào)性維護(hù)”和單調(diào)隊列有異曲同工之處。還有一種做法用一個主棧加一個輔助棧也屬于空間換時間的思路。我提這個是想提醒你數(shù)據(jù)結(jié)構(gòu)往往是組合使用的別做了一道棧題就只想著棧。等訓(xùn)練營后面接觸到單調(diào)棧、堆那一類內(nèi)容時你會更深刻地感受到棧只是一個工具真正值錢的是“你能識別出問題在問什么”?；氐浇裉爝@兩道題我覺得最大的價值不是 AC 的瞬間而是把“最近元素優(yōu)先處理”這個模型真正建立了。有了這個能力后面再碰表達(dá)式求值、逆波蘭表達(dá)式、簡化路徑、接雨水、柱狀圖中最大的矩形思路會順很多。我個人在實際刷題時還有個習(xí)慣每道棧題寫完都手動跑三個特殊例子——空輸入、單個字符、全部重復(fù)字符。這三個例子能一次性暴露?？蘸脱h(huán)結(jié)束后的狀態(tài)問題也推薦你試試。