1. 先讀懂題面有效括號(hào)子串到底在考什么1.1 題面解讀與兩個(gè)關(guān)鍵限制力扣熱題100刷到第32期這天我發(fā)現(xiàn)一個(gè)特別巧的對(duì)應(yīng)本期題號(hào)是32題目本身在力扣里的編號(hào)也是32——《最長有效括號(hào)》。這道題在Hard里屬于那種一眼能讀懂、暴力能寫出來、但優(yōu)雅解法要憋半天的典型也是動(dòng)態(tài)規(guī)劃和棧兩派思路交鋒最激烈的戰(zhàn)場之一。題目要求很簡單給定一個(gè)只包含 ( 和 ) 的字符串找出最長有效括號(hào)子串的長度。你看既沒有復(fù)雜的數(shù)據(jù)結(jié)構(gòu)定義也沒有繞來繞去的邊界約定可一旦動(dòng)手設(shè)計(jì)O(n)解法立刻就會(huì)撞上兩個(gè)流派的選擇難題是用棧去模擬括號(hào)配對(duì)還是用動(dòng)態(tài)規(guī)劃去推導(dǎo)狀態(tài)轉(zhuǎn)移這篇文章我會(huì)把三種主流解法全部拆開講清楚棧、動(dòng)態(tài)規(guī)劃、以及一個(gè)很多人不知道的O(1)空間雙向掃描法。刷題主力適合進(jìn)來對(duì)答案準(zhǔn)備面試的朋友可以重點(diǎn)看第5節(jié)的選型策略和邊界用例清單。老規(guī)矩不講虛的直接上硬貨。先摳字眼。子串二字決定了答案必須是連續(xù)的一段不能像子序列那樣跳著選。比如 ()(() 這個(gè)串肉眼能看到兩對(duì)獨(dú)立的 ()但中間隔了一個(gè)孤立的 (最長有效子串長度就是 2而不是 4。所有括號(hào)類題目都容易在連續(xù)這個(gè)前提上想當(dāng)然我最早刷這道題時(shí)也差點(diǎn)把子序列的思路帶進(jìn)來好在用例自測時(shí)及時(shí)發(fā)現(xiàn)。再來看有效的定義。一段括號(hào)子串有效需要同時(shí)滿足三個(gè)條件左右括號(hào)數(shù)量相等任意前綴中右括號(hào)數(shù)量不超過左括號(hào)數(shù)量整體能夠完整配對(duì)。前兩條合在一起其實(shí)就是在說這串括號(hào)可以被完整消去中間沒有任何刺頭。這也是后面所有解法的共同出發(fā)點(diǎn)——你判斷的永遠(yuǎn)不是一個(gè)孤立的括號(hào)而是一段可以閉環(huán)的區(qū)間。1.2 暴力法的天花板在哪里最直覺的思路是枚舉所有子串再驗(yàn)證復(fù)雜度 O(n3)這種解法在面試?yán)镏荒苡脕泶_認(rèn)題意沒有任何實(shí)用價(jià)值。稍微優(yōu)化一下固定起點(diǎn)向右擴(kuò)展用一個(gè)計(jì)數(shù)器 bal 維護(hù)左括號(hào)減右括號(hào)bal 為負(fù)立即中斷當(dāng)前起點(diǎn)bal 歸零時(shí)更新答案。這樣枚舉所有起點(diǎn)復(fù)雜度降到 O(n2)。def longest_valid_bruteforce(s: str) - int: n, ans len(s), 0 for start in range(n): bal 0 for end in range(start, n): bal 1 if s[end] ( else -1 if bal 0: break if bal 0: ans max(ans, end - start 1) return ans我建議你拿到題目后先在紙上把這段代碼寫一遍再去想優(yōu)化。為什么要這么做因?yàn)槭裁磿r(shí)候必須重置這個(gè)問題正是整道題的核心。暴力法里bal 一旦變成負(fù)數(shù)就必須中斷重新開始而所有 O(n) 解法本質(zhì)上都是在不同的數(shù)據(jù)結(jié)構(gòu)里維護(hù)這個(gè)重置點(diǎn)——棧用下標(biāo)記錄它DP 用狀態(tài)編碼它雙向掃描用計(jì)數(shù)器直接清零它。想通了這條線索三種解法就不再是三個(gè)孤立技巧而是同一件事的三副面孔。1.3 三個(gè)隱藏性質(zhì)把 O(n) 的路鋪好順著暴力法的思路往下挖能總結(jié)出三條對(duì)解題至關(guān)重要的性質(zhì)。第一有效子串不可能以 ( 結(jié)尾。結(jié)尾若多一個(gè)左括號(hào)整體左右數(shù)量必然失衡所以答案子串的最后一個(gè)字符一定是 )。反過來有效子串也不可能以一個(gè)多余的右括號(hào)開頭否則前綴里右括號(hào)數(shù)量必然超標(biāo)。第二括號(hào)配對(duì)滿足就近匹配的嵌套結(jié)構(gòu)。這種結(jié)構(gòu)天然適合用棧來模擬就像我們手工消括號(hào)時(shí)總先消最里面那一對(duì)。同時(shí)每一段有效括號(hào)的長度可以作為狀態(tài)向后傳導(dǎo)這也給動(dòng)態(tài)規(guī)劃留了門。第三相鄰的兩段有效子串拼接起來仍是有效子串。()() 就是兩個(gè) () 拼出來的長度可以直接相加()(()) 更是拼接和嵌套同時(shí)發(fā)生。這條性質(zhì)決定了 DP 里那些續(xù)接操作是合法的也決定了棧解法里棧頂?shù)疆?dāng)前位置之間的區(qū)間可以放心計(jì)算長度。下面我按棧 → 動(dòng)態(tài)規(guī)劃 → 雙向掃描的順序逐個(gè)拆解。三種解法的時(shí)間復(fù)雜度都是 O(n)但空間、思維門檻和代碼風(fēng)格差別很大你可以在最后對(duì)照自己的習(xí)慣選型。2. 棧解法下標(biāo)記賬一次遍歷找出所有有效段2.1 為什么棧里存的是下標(biāo)不是字符很多人刷過第20題《有效的括號(hào)》習(xí)慣性在棧里塞 ( 或 ) 字符。那道題只問整個(gè)字符串是否有效字符夠用但這道題問的是最長連續(xù)長度棧里必須存下標(biāo)。原因很簡單只有下標(biāo)才能算出兩個(gè)匹配括號(hào)之間的距離而這個(gè)距離就是有效子串的長度。更關(guān)鍵的是棧頂下標(biāo)的語義不是當(dāng)前括號(hào)而是最近一個(gè)沒有被匹配掉的位置。從它到當(dāng)前位置 i 之間的整段內(nèi)容一定是連續(xù)且有效的括號(hào)組合因?yàn)橹虚g只要出現(xiàn)過一個(gè)多余的括號(hào)它早就被彈出棧或者壓入棧當(dāng)作斷點(diǎn)了。如果棧里只存字符這種位置信息完全丟失長度無從談起。我自己就是從20題的慣性里帶出來的受害者第一版代碼棧里存括號(hào)字符跑完立刻意識(shí)到根本沒法算長度白白浪費(fèi)了十分鐘。所以棧解法的第一原則存下標(biāo)不存字符。下標(biāo)既是配對(duì)憑證也是長度計(jì)算的刻度尺。2.2 哨兵 -1一個(gè)被很多人忽略的細(xì)節(jié)初始把 -1 壓入棧它的作用有兩層。第一它充當(dāng)基準(zhǔn)線。當(dāng) s 本身就以有效子串開頭時(shí)比如 ()計(jì)算長度需要用到棧底的位置 -1i1 時(shí)彈出 0 后棧頂是 -1長度 1-(-1)2。如果棧初始為空這個(gè)長度是算不出來的你還得額外寫分支去處理第一個(gè)字符就是左括號(hào)的情況代碼立刻丑一倍。第二它統(tǒng)一了?？盏臓顟B(tài)判斷。遇到 ) 彈出后如果棧為空說明這個(gè)右括號(hào)沒有匹配對(duì)象它就是新的一段有效子串開始之前的斷點(diǎn)于是把它的下標(biāo)壓棧作為下一條基準(zhǔn)線。有 -1 在底下墊著?？者@個(gè)分支的業(yè)務(wù)邏輯非常清晰不需要再區(qū)別對(duì)待。提示很多題解會(huì)把 -1 解釋成虛擬的左括號(hào)前一位這個(gè)說法有點(diǎn)抽象。我更愿意把它理解成一個(gè)樸素的基準(zhǔn)線——它就是整個(gè)字符串開始之前的位置任何從下標(biāo)0開始的括號(hào)配對(duì)都要從這條線上量距離。2.3 代碼實(shí)現(xiàn)與三個(gè)分支的推演def longest_valid_parentheses(s: str) - int: stack [-1] ans 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: ans max(ans, i - stack[-1]) return ans邏輯就三個(gè)分支。左括號(hào)無條件入棧相當(dāng)于記下一筆待配對(duì)的賬。遇到右括號(hào)先嘗試從賬本里銷掉一個(gè)左括號(hào)如果賬本空了說明當(dāng)前右括號(hào)是多余的它本身變成新賬本的起點(diǎn)如果賬本還有貨銷掉之后棧頂就是最近未匹配位置用它當(dāng)起點(diǎn)來計(jì)算最新有效段的長度。這里有一個(gè)極容易寫錯(cuò)的分支順序很多人把更新答案寫在了?？张袛嗲懊鎸?dǎo)致剛彈出的 -1 或者剛壓入的斷點(diǎn)被當(dāng)成合法左邊界算出的長度全是錯(cuò)的。比如輸入 ()正確流程是先彈出0看到棧頂是 -1再算 1-(-1)2如果順序?qū)懛礂?pop 后還沒來得及判斷就立刻取棧頂棧頂變成了0算出來的長度變成1答案當(dāng)場掛掉。Java 版本順手也給了面試時(shí)用慣哪個(gè)就用哪個(gè)。要點(diǎn)是必須用 Deque 模擬棧不要用 Stack 類。public int longestValidParentheses(String s) { DequeInteger stack new ArrayDeque(); stack.push(-1); int ans 0; for (int i 0; i s.length(); i) { if (s.charAt(i) () { stack.push(i); } else { stack.pop(); if (stack.isEmpty()) { stack.push(i); } else { ans Math.max(ans, i - stack.peek()); } } } return ans; }2.4 兩個(gè)經(jīng)典用例的逐步模擬先看 (()。這個(gè)用例專測左括號(hào)盈余的情況很多解法在這里會(huì)算錯(cuò)。步驟字符操作棧內(nèi)容答案0初始化壓入 -1[-1]01(push 0[-1, 0]02(push 1[-1, 0, 1]03)pop 1棧頂 0[-1, 0]2答案 2來自下標(biāo) 1-2 之間的 ()。注意這里如果棧里沒有 -1 墊底pop 之后棧空邏輯會(huì)直接斷掉后面的長度計(jì)算全亂。再看標(biāo)準(zhǔn)范例 )()())它前后都有多余的右括號(hào)最能體現(xiàn)斷點(diǎn)思想步驟字符操作棧內(nèi)容答案0初始化壓入 -1[-1]01)pop -1?？誴ush 0[0]02(push 1[0, 1]03)pop 1棧頂 0[0]14(push 3[0, 3]15)pop 3棧頂 0[0]46)pop 0?？誴ush 5[5]4答案 4對(duì)應(yīng)下標(biāo) 1-4 的 ()()。下標(biāo) 0 和 5 的兩個(gè)多余右括號(hào)分別充當(dāng)了兩段有效區(qū)的斷點(diǎn)。這就是棧解法的本質(zhì)它把有效的連續(xù)段用一個(gè)個(gè)斷點(diǎn)切分開來實(shí)時(shí)維護(hù)最大段長。整個(gè)過程只遍歷一次字符串時(shí)間 O(n)空間最壞 O(n)。3. 動(dòng)態(tài)規(guī)劃解法dp[i] 的兩種轉(zhuǎn)移才是精髓3.1 狀態(tài)定義為什么必須以 s[i] 結(jié)尾棧解法很直觀但面試官一旦追問能不能用動(dòng)態(tài)規(guī)劃你就要拿出另一套完全不同的視角。動(dòng)態(tài)規(guī)劃這里常見的誤區(qū)是定義 dp[i] 為前 i 個(gè)字符中的最長有效括號(hào)長度。這樣定義做轉(zhuǎn)移會(huì)很別扭因?yàn)橛行ё哟仨氃诋?dāng)前位置剛好結(jié)束才能向后拼接如果定義成全局最大值你根本不知道上一段有效子串在哪兒結(jié)束也就無法判斷當(dāng)前這個(gè) ) 能不能接上去。所以標(biāo)準(zhǔn)做法是定義 dp[i] 為以 s[i] 結(jié)尾的最長有效括號(hào)子串長度。這個(gè)以誰結(jié)尾的視角是線性 dp 里非常核心的套路與其統(tǒng)計(jì)全局不如精確到每個(gè)位置的局部狀態(tài)。它犧牲了一點(diǎn)直覺換來了轉(zhuǎn)移方程的可計(jì)算性。由第1節(jié)的性質(zhì)可知有效子串不可能以 ( 結(jié)尾所以但凡 s[i](dp[i] 直接等于 0只有 s[i]) 才需要認(rèn)真推導(dǎo)。3.2 轉(zhuǎn)移一配成 () 的直接拼接如果 s[i-1] (那 s[i-1] 和 s[i] 剛好配成最內(nèi)層的 ()長度至少有 2。如果 i-2 位置還存在一段有效的子串這段子串與 () 相鄰拼接后仍然有效所以dp[i] dp[i-2] 2類比一下這就像在一條已經(jīng)鋪好的鐵軌上再接一段長度直接累加。邊界是 i-2 0 時(shí)dp[i-2] 按 0 處理() 在最開頭也是一種合法狀態(tài)。這個(gè)轉(zhuǎn)移最簡單但它負(fù)責(zé)處理所有平鋪直敘的拼接場景比如 ()() 的第二個(gè)括號(hào)。3.3 轉(zhuǎn)移二外層嵌套與左邊續(xù)接如果 s[i-1] )說明 s[i] 不能和 s[i-1] 直接配對(duì)它必須翻過一段已經(jīng)形成的有效子串去匹配更早的一個(gè) (。具體來說令 j i - dp[i-1] - 1這個(gè) j 是以 s[i-1] 結(jié)尾的那段有效子串左邊緊鄰的位置。如果 j 0 且 s[j] (那么 s[j] 和 s[i] 配對(duì)成功把 dp[i-1] 那整段包在了中間外層的長度是 dp[i-1] 2再往前看j-1 位置若也有有效子串繼續(xù)拼接于是dp[i] dp[i-1] 2 dp[j-1]當(dāng) j-1 0 時(shí)dp[j-1] 按 0 處理這個(gè)轉(zhuǎn)移是整道 DP 解法的勝負(fù)手。它同時(shí)處理了兩層含義內(nèi)層已有的連續(xù)段被外層括號(hào)包裹后依然有效并且包裹之后還能和左邊另一段有效子串手拉手連成長串。沒有后面那個(gè) dp[j-1]遇到 ()(()) 這種外層包著內(nèi)層、左邊還連著一截的結(jié)構(gòu)就會(huì)漏算。3.4 完整代碼與下標(biāo)越界的三個(gè)坑def longest_valid_parentheses_dp(s: str) - int: n len(s) dp [0] * n ans 0 for i in range(1, n): if s[i] ): if s[i-1] (: dp[i] (dp[i-2] if i 2 else 0) 2 else: j i - dp[i-1] - 1 if j 0 and s[j] (: dp[i] dp[i-1] 2 (dp[j-1] if j 1 else 0) ans max(ans, dp[i]) return ans三個(gè)坑我在實(shí)際寫的時(shí)候全部踩過一遍逐個(gè)說。第一i-2 可能越界。Python 里 dp[-1] 不會(huì)報(bào)錯(cuò)但會(huì)默默拿到數(shù)組最后一個(gè)元素結(jié)果全錯(cuò)。必須用 i 2 顯式判斷。我第一次寫就是直接 dp[i-2] 2短用例全過一到 () 開頭的長串就出詭異結(jié)果排查了半天才發(fā)現(xiàn)是負(fù)下標(biāo)在搗鬼。第二j 可能為負(fù)。j 小于 0 說明 s[i] 左邊連一段有效子串都不存在直接跳過不能訪問 s[j]。Python 的 s[-1] 是合法語法但語義完全錯(cuò)誤——它會(huì)取到字符串最后一個(gè)字符這種負(fù)下標(biāo)陷阱最容易在做自測時(shí)漏掉因?yàn)槎逃美?j 常常恰好不小于 0。第三dp[j-1] 的取值。j-1 等于 -1 時(shí)按 0 算否則取 dp[j-1]。這里一旦貪圖省事直接寫成 dp[j-1] ...遇到 () 這種短例子可能僥幸通過但遇到 ()() 就會(huì)在 i3 時(shí)算出差之千里的結(jié)果。用一個(gè)嵌套加拼接的綜合例子驗(yàn)證()(())。dp 數(shù)組從 0 到 5 的推演如下i字符轉(zhuǎn)移路徑dp[i]0(左括號(hào)直接置001)s[0](dp[1]dp[-1]222(左括號(hào)直接置003(左括號(hào)直接置004)s[3](dp[4]dp[2]225)s[4])j5-2-12s[2](dp[5]dp[4]2dp[1]6最終答案 6整串有效。注意 dp[5] 那一行內(nèi)層 dp[4]2 對(duì)應(yīng)下標(biāo) 3-4 的 ()s[2]( 與 s[5]) 在外部配對(duì)然后左邊續(xù)上 dp[1]2 也就是下標(biāo) 0-1 的 ()三段合體為 ()(())。這就是轉(zhuǎn)移二把嵌套和拼接一并解決的威力少了 dp[j-1] 那一項(xiàng)正確答案會(huì)變成 4。4. 常數(shù)空間雙向掃描打敗所有輔助結(jié)構(gòu)的野路子4.1 一次掃描為什么不夠棧和 DP 的空間都是 O(n)于是很多人開始想能不能用一個(gè)計(jì)數(shù)器從左往右掃一遍就把答案算出來思路是這樣的left 記錄左括號(hào)數(shù)right 記錄右括號(hào)數(shù)。right 超過 left 時(shí)清零重來left 等于 right 時(shí)更新答案。這個(gè)方法對(duì) )()()) 有效但拿 (() 試一下就會(huì)發(fā)現(xiàn)掃描到結(jié)尾時(shí) left2、right1左右始終不相等答案一直是 0可正確答案明明是 2。問題出在多余的那個(gè) ( 在字符串末尾正向掃描時(shí)它從來不觸發(fā)清零條件反而一直壓著計(jì)數(shù)器讓內(nèi)部那個(gè) () 永遠(yuǎn)等不到 leftright 的時(shí)刻。換句話說正向掃描能識(shí)別所有右括號(hào)盈余型的字符串但遇到左括號(hào)盈余型就抓瞎了。4.2 反向掃描的鏡像規(guī)則把字符串倒過來再掃一遍問題就迎刃而解。反向掃描時(shí)規(guī)則的左右鏡像互換遇到 ) 給 right 加一遇到 ( 給 left 加一當(dāng) left 超過 right 時(shí)清零重來因?yàn)閺挠彝罂炊喑鰜淼淖罄ㄌ?hào)才是錯(cuò)誤方向的產(chǎn)物left 等于 right 時(shí)更新答案。(() 在反向掃描中是這樣的從右往左依次是 )、(、(。掃到 ) 時(shí) right1掃到第一個(gè) ( 時(shí) left1兩者相等更新答案為 2。隨后又掃到多余的 (觸發(fā) leftright 清零但答案已經(jīng)拿到了。這個(gè)鏡像思想很有意思一個(gè)方向無法平衡的括號(hào)顛倒視角后反而能正確配對(duì)。很多 O(1) 空間的題解都藏著類似的換方向看問題的哲學(xué)。4.3 代碼實(shí)現(xiàn)與為什么雙向不會(huì)漏def longest_valid_parentheses_scan(s: str) - int: ans 0 left right 0 for ch in s: if ch (: left 1 else: right 1 if left right: ans max(ans, 2 * right) elif right left: left right 0 left right 0 for ch in reversed(s): if ch ): right 1 else: left 1 if left right: ans max(ans, 2 * left) elif left right: left right 0 return ans現(xiàn)在解釋為什么正反各掃一次就不會(huì)漏解。任意一個(gè)有效子串如果正向掃描時(shí)錯(cuò)過了說明它左邊存在一些盈余的左括號(hào)一直壓著計(jì)數(shù)讓它內(nèi)部的 leftright 狀態(tài)無法達(dá)成。但盈余左括號(hào)在反向掃描里恰好屬于錯(cuò)誤方向——反向規(guī)則會(huì)在遇到它們之前正常配對(duì)因此這個(gè)子串在反向掃描里會(huì)被正確識(shí)別。反過來如果正向掃描命中了反向掃描最多是重復(fù)命中一次取最大值不會(huì)出錯(cuò)。這個(gè)方案的復(fù)雜度是 O(n) 時(shí)間、O(1) 空間比棧和 DP 都省內(nèi)存。代價(jià)是思維跳躍面試時(shí)第一次聽的人往往會(huì)愣一下但一旦講明白就是全場最佳的程序員的浪漫。日常刷題時(shí)我也常拿它當(dāng)最終優(yōu)化手段畢竟寫慣了 O(n) 空間能省下幾個(gè) MB 總是舒服的。5. 三方案巔峰對(duì)決面試選型與我的實(shí)戰(zhàn)踩坑5.1 橫向?qū)Ρ日l更快誰更好寫誰最省空間解法時(shí)間復(fù)雜度空間復(fù)雜度核心思路實(shí)現(xiàn)難度典型失誤棧O(n)O(n)用下標(biāo)賬本記錄斷點(diǎn)與配對(duì)較低棧里存字符、忘記 -1 哨兵動(dòng)態(tài)規(guī)劃O(n)O(n)以 s[i] 結(jié)尾的狀態(tài)轉(zhuǎn)移中等負(fù)下標(biāo)越界、轉(zhuǎn)移條件漏判雙向掃描O(n)O(1)雙向計(jì)數(shù)配對(duì)盈余括號(hào)自動(dòng)出局中等反向清零條件寫反時(shí)間上三者平手真正的分水嶺在空間和思維門檻。棧解法最貼近人腦直覺代碼最短出錯(cuò)率也最低適合絕大多數(shù)面試場景DP 解法展示了你對(duì)狀態(tài)轉(zhuǎn)移的掌控力適合在討論線性 dp時(shí)展開雙向掃描空間最省是三分鐘內(nèi)的最優(yōu)展示但對(duì)方向感的考察非常嚴(yán)格寫反一個(gè)清零條件就全盤皆輸。5.2 面試現(xiàn)場的出牌順序建議我的實(shí)戰(zhàn)習(xí)慣是三步走。第一步先給出 O(n2) 的計(jì)數(shù)擴(kuò)展法確認(rèn)題意讓面試官知道你沒有卡殼也給自己爭取思考時(shí)間。第二步立刻轉(zhuǎn)棧解法15 分鐘內(nèi)寫出干凈代碼這是保底分。第三步如果面試官追問能不能把空間壓到 O(1)再上雙向掃描。不要把 DP 放在第一個(gè)講。不是說 DP 不好而是它的轉(zhuǎn)移方程需要好幾個(gè)用例才能讓人信服編碼時(shí)間比棧長一旦下標(biāo)處理出錯(cuò)很難快速定位。棧解法在壓力環(huán)境下更穩(wěn)。如果面試官明確指定考動(dòng)態(tài)規(guī)劃那順序反過來先給出 dp 定義和轉(zhuǎn)移方程再用用例驗(yàn)證最后提一句這道題還有棧和 O(1) 掃描兩種思路展示廣度。兩種出牌方式都覆蓋了解題能力 溝通能力這兩個(gè)面試核心考察點(diǎn)。5.3 必須背下的邊界用例清單下面這組用例是我在本地寫單元測試時(shí)固定掛上的每寫一個(gè)解法就讓全部用例過一遍比隨機(jī)提交力扣有說服力得多。輸入期望輸出考察點(diǎn)0空串(0單左括號(hào))0單右括號(hào)()2最小有效段(()2左括號(hào)盈余專測反向掃描)()())4標(biāo)準(zhǔn)示例前后雜質(zhì)((()))6純嵌套()(())6拼接 嵌套混合(()())6多段拼接)))(((0左右分離全部無效特別是 (() 和 )))((( 這兩種盈余型用例三種解法里至少有兩道會(huì)在這里翻車。我把它們放在自測用例的前排任何一次重寫代碼都要先過這關(guān)已經(jīng)幫我攔下了不知道多少低級(jí)錯(cuò)誤。5.4 由第32題延伸出去的一串兄弟題括號(hào)類問題在算法面試?yán)锸莻€(gè)大家族掌握了這道題的三種視角再刷下面這些題會(huì)輕松很多。第20題《有效的括號(hào)》基礎(chǔ)配對(duì)棧存字符即可相當(dāng)于本道題棧解法的簡化版。第22題《括號(hào)生成》回溯生成所有合法括號(hào)組合涉及卡特蘭數(shù)直覺。第678題《有效的括號(hào)字符串》加入 * 通配符雙向掃描的計(jì)數(shù)思想直接派上用場。第921題《使括號(hào)有效的最少添加》單向計(jì)數(shù)即可是雙向掃描思路的降維應(yīng)用。第1541題《平衡括號(hào)字符串的最少插入次數(shù)》同樣是計(jì)數(shù)法擴(kuò)展對(duì)左右括號(hào)的處理要更細(xì)。我個(gè)人刷題是一拖五策略一道核心題講透立刻把相關(guān)題一次性做完。這套括號(hào)家族刷下來對(duì)棧、線性 dp、貪心計(jì)數(shù)三種范式都會(huì)形成肌肉記憶之后再遇到任何括號(hào)題十分鐘內(nèi)就能定位到正確解法。最后說一點(diǎn)個(gè)人體會(huì)。第32題最值錢的地方不是讓你背下三種解法而是讓你形成一種條件反射看到成對(duì)出現(xiàn)、可嵌套、可拼接的結(jié)構(gòu)同時(shí)想到棧和以終點(diǎn)為狀態(tài)的 dp 兩條建模路徑。我自己每次刷完一道解法會(huì)把另外兩種解法也各寫一遍互相印證答案一旦兩個(gè)解法輸出不一致先別急著改代碼而是拿最短的用例從頭手工模擬一步一步對(duì)齊狀態(tài)值。這道題里我靠這個(gè)習(xí)慣抓到過至少兩次下標(biāo)越界也靠它徹底搞懂了 dp[i] 轉(zhuǎn)移二那行公式。希望這篇拆解也能給你同樣的踏實(shí)感。