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