如果只能選一道題來(lái)理解棧這種數(shù)據(jù)結(jié)構(gòu)我會(huì)選 LeetCode 第 20 題——有效的括號(hào)。這道題沒(méi)有復(fù)雜的數(shù)學(xué)推導(dǎo)也不需要精巧的二分優(yōu)化但它把棧的核心語(yǔ)義展示得淋漓盡致。作為一個(gè)刷過(guò)幾百道題、也在面試現(xiàn)場(chǎng)看過(guò)別人寫(xiě)這道題的過(guò)來(lái)人我可以很明確地說(shuō)這道題值得你反復(fù)做三遍。它不僅僅是一個(gè)入門級(jí)的熱身題更是一把打開(kāi)棧這一數(shù)據(jù)結(jié)構(gòu)大門的鑰匙。無(wú)論你是剛接觸算法的新手還是準(zhǔn)備面試的求職者甚至是寫(xiě)過(guò)多年業(yè)務(wù)代碼但想補(bǔ)一補(bǔ)基本功的老開(kāi)發(fā)都能從這道題里收獲一些東西。括號(hào)匹配這個(gè)場(chǎng)景我們?cè)趯?xiě)代碼時(shí)其實(shí)經(jīng)常遇到——編譯器的語(yǔ)法檢查、編輯器的自動(dòng)補(bǔ)全、表達(dá)式求值里的括號(hào)優(yōu)先級(jí)處理底層都有一套類似判定括號(hào)是否合法的機(jī)制。它能幫你快速理解什么叫最近匹配什么叫后進(jìn)先出以及為什么要用棧而不是用簡(jiǎn)單的計(jì)數(shù)打天下。這篇文章我會(huì)從題目本身出發(fā)把思路拆解、代碼實(shí)現(xiàn)、邊界陷阱和常見(jiàn)錯(cuò)誤一次講透。1. 一道經(jīng)典題背后的核心思想1.1 題目到底在考什么先還原一下題目原貌給定一個(gè)只包含(、)、[、]、{、}六種字符的字符串判斷字符串中的括號(hào)是否都是有效閉合的。有效閉合的定義包括兩點(diǎn)左括號(hào)必須用相同類型的右括號(hào)閉合并且閉合順序要正確?？兆址梢暈橛行?。這個(gè)題在面試?yán)锍霈F(xiàn)的頻率高得嚇人。我統(tǒng)計(jì)過(guò)自己參與過(guò)的技術(shù)面試候選人第一輪手撕代碼碰到的題目里這道題至少占了兩成左右。它的定位很有意思說(shuō)難不難但很能反映基本功。有些人上來(lái)就寫(xiě)錯(cuò)了思路有些人寫(xiě)對(duì)了但邊界條件處理得稀爛還有些人根本不知道 Java 里應(yīng)該用ArrayDeque而不是Stack——這些細(xì)節(jié)往往比 AC 本身更能讓面試官看清一個(gè)人的水平。它到底在考什么說(shuō)穿了就三個(gè)東西第一你認(rèn)不認(rèn)得棧這個(gè)數(shù)據(jù)結(jié)構(gòu)第二你能不能把現(xiàn)實(shí)問(wèn)題抽象成棧的入棧、出棧操作第三你的代碼能不能處理干凈各種邊界條件。這三點(diǎn)對(duì)應(yīng)的是數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)、抽象建模能力和代碼嚴(yán)謹(jǐn)性面試官想要的就是這三樣。順便說(shuō)一句這道題也是很多刷題網(wǎng)站和課程安排里的棧專題第一題。它就像棧類題目里的Hello World你要是能把這道題吃透后面再去碰單調(diào)棧、表達(dá)式求值、函數(shù)調(diào)用棧相關(guān)的題都會(huì)順暢很多。1.2 括號(hào)匹配的本質(zhì)最近匹配原則為什么括號(hào)匹配能和棧扯上關(guān)系關(guān)鍵在于括號(hào)天然有一個(gè)性質(zhì)一個(gè)右括號(hào)要和它左側(cè)最近的那個(gè)左括號(hào)配對(duì)而不是隨便找一個(gè)左括號(hào)配對(duì)。舉個(gè)例子看字符串([])。外層左括號(hào)(最先出現(xiàn)但匹配它的右括號(hào))反而最后才出現(xiàn)內(nèi)層[次出現(xiàn)對(duì)應(yīng)的]卻更早出現(xiàn)。這種越早出現(xiàn)的左括號(hào)越晚被匹配的規(guī)律恰恰就是后進(jìn)先出LIFO的語(yǔ)義棧頂永遠(yuǎn)是最后壓入的元素也就永遠(yuǎn)是最新、最近的待匹配項(xiàng)。生活里的類比也很好理解你往桌上一疊盤子最后放上去的那個(gè)盤子總是你最先要取下來(lái)的那個(gè)。括號(hào)匹配里的嵌套結(jié)構(gòu)本質(zhì)上就是這樣一疊待匹配的左括號(hào)。每當(dāng)遇到一個(gè)右括號(hào)你只能從這疊盤子的頂部取一個(gè)左括號(hào)來(lái)配對(duì)不能跳過(guò)去取底部的。一旦取了底部那個(gè)上面的順序就亂套了。這個(gè)最近匹配原則是整個(gè)題目的靈魂。理解了它你不僅能寫(xiě)出正確答案還能跟面試官解釋清楚為什么這道題不能用簡(jiǎn)單的數(shù)量統(tǒng)計(jì)來(lái)做。這個(gè)點(diǎn)后面我會(huì)單獨(dú)展開(kāi)講。2. 為什么棧是這道題的答案2.1 計(jì)數(shù)法的致命缺陷我知道很多人第一眼看到這道題的反應(yīng)是統(tǒng)計(jì)一下左右括號(hào)的數(shù)量看它們相不相等不就行了這個(gè)思路在最簡(jiǎn)單的用例下確實(shí)能蒙混過(guò)關(guān)。比如()左括號(hào) 1 個(gè)右括號(hào) 1 個(gè)相等通過(guò)。又比如[]{}三種括號(hào)各一對(duì)數(shù)量也平衡看起來(lái)也通過(guò)了。但稍微給一點(diǎn)復(fù)雜的結(jié)構(gòu)這個(gè)方案立刻露餡。經(jīng)典反例是([)]。這個(gè)字符串里左括號(hào)有兩個(gè)(和[右括號(hào)也有兩個(gè))和]數(shù)量上完全相等。如果你只做數(shù)量統(tǒng)計(jì)會(huì)判定它是合法的。但它真的是合法的嗎不是。因?yàn)?應(yīng)該匹配)[應(yīng)該匹配]而這個(gè)字符串里兩個(gè)右括號(hào)把兩個(gè)左括號(hào)交叉了(的左括號(hào)在[和]的外面可它的右括號(hào))卻落在]的里面。這種交叉嵌套不合任何語(yǔ)言的語(yǔ)法規(guī)則。所以數(shù)量相等只是必要條件遠(yuǎn)不是充分條件。判斷括號(hào)是否合法不僅要看左右數(shù)量對(duì)得上還要看配對(duì)順序?qū)Φ蒙?。?jì)數(shù)法把順序信息完全丟掉了這是它的致命傷。如果你在面試?yán)锾岢鲇?jì)數(shù)法面試官大概率會(huì)追問(wèn)一句([)]你怎么判斷這一問(wèn)就能讓你意識(shí)到問(wèn)題所在。2.2 棧的數(shù)據(jù)結(jié)構(gòu)特性與匹配過(guò)程的映射現(xiàn)在來(lái)看棧是怎么把最近匹配翻譯成程序的。算法的核心思路只有四步遍歷字符串的每個(gè)字符如果是左括號(hào)(、[、{把它壓入棧如果是右括號(hào))、]、}從棧頂取出一個(gè)左括號(hào)檢查兩者是否是同一類型的一對(duì)如果棧頂元素不是配對(duì)的左括號(hào)或者棧里根本沒(méi)有元素直接判定不合法遍歷結(jié)束后如果棧不為空說(shuō)明有左括號(hào)沒(méi)找到配對(duì)也不合法。我拿({[]})這個(gè)合法嵌套的例子走一遍。遍歷到(入棧棧變成[(]遍歷到{入棧棧變成[(, {]遍歷到[入棧棧變成[(, {, []遍歷到]是右括號(hào)看棧頂[剛好配對(duì)彈棧棧變回[(, {]遍歷到}看棧頂{配對(duì)彈棧棧變成[(]遍歷到)看棧頂(配對(duì)彈棧棧變成[]。最后棧為空返回合法。整個(gè)過(guò)程就像按下一個(gè)按鈕逐層剝開(kāi)嵌套結(jié)構(gòu)。這套邏輯把最近匹配直接轉(zhuǎn)化成了棧頂匹配。為什么棧頂就是最近因?yàn)闂ｍ斢肋h(yuǎn)是最新壓入的那個(gè)左括號(hào)也就是當(dāng)前所有未匹配左括號(hào)中最新出現(xiàn)的那個(gè)。右括號(hào)要找的恰好就是它。這個(gè)映射關(guān)系非常自然沒(méi)有任何生搬硬套。2.3 兩種常見(jiàn)實(shí)現(xiàn)風(fēng)格對(duì)比實(shí)現(xiàn)上有兩種主流風(fēng)格。第一種只壓左括號(hào)。遇到左括號(hào)入棧遇到右括號(hào)做匹配判斷。這種寫(xiě)法最直白三種括號(hào)的配對(duì)關(guān)系可以用哈希表存起來(lái)也可以寫(xiě)成switch。第二種所有括號(hào)都?jí)簵Ｓ龅接依ㄌ?hào)時(shí)再把棧頂彈出來(lái)比較如果棧頂也是右括號(hào)或者匹配不上就返回False。第二種寫(xiě)法其實(shí)更繞不推薦因?yàn)樗炎罄ㄌ?hào)和右括號(hào)混在同一個(gè)棧里棧頂?shù)呐袛噙壿嫹炊儚?fù)雜了。在面試場(chǎng)景里我強(qiáng)烈推薦第一種寫(xiě)法并且用哈希表存儲(chǔ)配對(duì)關(guān)系。理由有兩個(gè)其一代碼里每個(gè)分支的意圖非常清晰——if判斷是不是右括號(hào)是就匹配不是就入棧面試官掃一眼就能看明白其二哈希表比一長(zhǎng)串if-else更容易維護(hù)后續(xù)要擴(kuò)展新的括號(hào)類型也方便。省下來(lái)的時(shí)間可以用來(lái)跟面試官討論邊界情況這在面試?yán)锸羌臃猪?xiàng)。3. 完整實(shí)操手寫(xiě)一套高效判定3.1 以 Python 為例的完整實(shí)現(xiàn)先說(shuō) Python 版本這是我在 LeetCode 上反復(fù)使用的一版代碼短但五臟俱全。def isValid(s: str) - bool: pairs {): (, ]: [, }: {} stack [] for char in s: # 當(dāng)前字符是右括號(hào) if char in pairs: # 棧為空或棧頂不是配對(duì)的左括號(hào) if not stack or stack[-1] ! pairs[char]: return False stack.pop() else: # 當(dāng)前字符是左括號(hào)入棧 stack.append(char) # 棧空說(shuō)明全部配對(duì)成功 return not stack逐行解釋一下。pairs這個(gè)字典定義的是配對(duì)關(guān)系注意鍵是右括號(hào)值是左括號(hào)方向別搞反了。遍歷時(shí)char in pairs這一句就是判斷當(dāng)前字符是不是右括號(hào)時(shí)間復(fù)雜度是 O(1)因?yàn)樽值涞讓邮枪１?。如果是右括?hào)先看?？詹豢湛諚Ｕf(shuō)明這個(gè)右括號(hào)是個(gè)孤兒前面沒(méi)有任何左括號(hào)等它直接返回False再看棧頂元素是不是它期待的那個(gè)左括號(hào)不是也直接返回False。這兩步都通過(guò)了才執(zhí)行pop。如果是左括號(hào)不管具體是哪種直接append進(jìn)棧。最后一行return not stack很經(jīng)典棧為空說(shuō)明所有左括號(hào)都成功配對(duì)了返回True棧不為空說(shuō)明至少有一個(gè)左括號(hào)被晾在棧里返回False。這個(gè)寫(xiě)法用 Python 的布爾語(yǔ)義把判斷壓縮成一行簡(jiǎn)潔又不容易漏。3.2 以 Java 為例的完整實(shí)現(xiàn)很多面試是用 Java 考的所以 Java 版本也必須拿得出手。這里有一個(gè)很多新手不知道的坑不要用java.util.Stack要用ArrayDeque。class Solution { public boolean isValid(String s) { DequeCharacter stack new ArrayDeque(); MapCharacter, Character pairs new HashMap() {{ put(), (); put(], [); put(}, {); }}; for (char c : s.toCharArray()) { if (pairs.containsKey(c)) { if (stack.isEmpty() || stack.pop() ! pairs.get(c)) { return false; } } else { stack.push(c); } } return stack.isEmpty(); } }先說(shuō)為什么不用Stack。Stack是 Java 早期遺留的類繼承自Vector而Vector的幾乎所有方法都加了synchronized鎖。在單線程算法題場(chǎng)景里這個(gè)鎖只有開(kāi)銷、沒(méi)有收益。ArrayDeque是雙端隊(duì)列當(dāng)棧用的時(shí)候性能更好官方文檔也明確建議優(yōu)先使用。面試時(shí)你能說(shuō)出這個(gè)區(qū)別本身就是技術(shù)深度的體現(xiàn)。再看看這段代碼里的細(xì)節(jié)。初始化哈希表時(shí)我用了雙括號(hào)寫(xiě)法這在面試題里無(wú)傷大雅但要知道它每次會(huì)生成一個(gè)匿名內(nèi)部類正式項(xiàng)目里不推薦。更嚴(yán)格的寫(xiě)法是在構(gòu)造函數(shù)里初始化。核心判斷邏輯在stack.isEmpty() || stack.pop() ! pairs.get(c)這一行——利用||的短路求值如果棧為空就不會(huì)執(zhí)行后面的pop避免了空棧異常。這在邏輯上和 Python 版本的if not stack or stack[-1] ! pairs[char]完全等價(jià)。3.3 關(guān)鍵分支邏輯逐行解讀我自己在指導(dǎo)別人寫(xiě)這道題時(shí)發(fā)現(xiàn)最容易出問(wèn)題的就是那個(gè)匹配分支的判斷順序。每次遇到右括號(hào)其實(shí)是一次匹配請(qǐng)求。這個(gè)請(qǐng)求有兩個(gè)前置條件缺一不可棧里必須有元素。棧為空說(shuō)明當(dāng)前右括號(hào)前面沒(méi)有等待配對(duì)的左括號(hào)比如字符串就是)這種情況棧頂元素必須正好是它的另一半。比如當(dāng)前是)棧頂必須是(而不是[或{。我見(jiàn)過(guò)不少只寫(xiě)了一半判斷的代碼比如只判斷棧頂元素是否匹配卻不判斷棧空if stack[-1] ! pairs[char]: # ?？諘r(shí)會(huì) IndexError return False這種寫(xiě)法在遇到以右括號(hào)開(kāi)頭的字符串時(shí)會(huì)直接拋異常。教訓(xùn)就一句話先判空再取值。這一點(diǎn)在 Python 里尤其重要因?yàn)闂？諘r(shí)訪問(wèn)stack[-1]會(huì)直接報(bào)IndexError而不是返回一個(gè)空值讓你好比較。Java 版本由于||短路求值的存在把判空和取值寫(xiě)在同一個(gè)表達(dá)式里天然安全但我還是建議你在心里明確這一步的邏輯而不是把它當(dāng)成一個(gè)理所當(dāng)然的寫(xiě)法。3.4 復(fù)雜度分析復(fù)雜度是面試的必問(wèn)環(huán)節(jié)。時(shí)間上每個(gè)字符最多入棧一次、出棧一次所有操作都是常數(shù)級(jí)別所以總時(shí)間復(fù)雜度是 O(n)?？臻g上最壞情況是字符串全由左括號(hào)組成比如(((((這時(shí)候棧里要存 n 個(gè)元素空間復(fù)雜度是 O(n)。這個(gè)復(fù)雜度結(jié)論本身不復(fù)雜但我想多說(shuō)一句這道題的線性復(fù)雜度并不稀罕在 LeetCode 32 題最長(zhǎng)有效括號(hào)里同樣的輸入可以玩出 O(n) 的 DP 配合棧、O(1) 的雙指針計(jì)數(shù)等花樣。所以這道基礎(chǔ)題不單是為了 AC它建立的是你對(duì)棧解決子串匹配類問(wèn)題的直覺(jué)后面所有變體都是在這個(gè)直覺(jué)上做加法。面試時(shí)把這段復(fù)雜度分析說(shuō)得有條理也能展示你的分析框架最壞情況、平均情況、空間占用一個(gè)一個(gè)來(lái)。4. 邊界情況與進(jìn)階陷阱4.1 空串與單字符很多題目喜歡在邊界條件上埋坑這道題也不例外?？兆址呛戏ǖ摹ｋm然有個(gè)別業(yè)務(wù)場(chǎng)景可能要求非空但 LeetCode 和絕大多數(shù)算法題對(duì)空串的默認(rèn)判定都是true。你可以理解成沒(méi)有任何括號(hào)需要配對(duì)自然也是有效閉合的。我在代碼里沒(méi)有對(duì)空串做特殊處理因?yàn)閞eturn not stack直接返回True天然正確。單個(gè)左括號(hào)(不合法。它走到最后一步時(shí)棧不為空被return not stack攔下。單個(gè)右括號(hào))也不合法它第一輪就會(huì)進(jìn)入右括號(hào)分支發(fā)現(xiàn)棧為空直接返回False。這兩個(gè)用例是筆試?yán)镒钊菀壮鲥e(cuò)的有人把遍歷邏輯寫(xiě)得復(fù)雜無(wú)比卻忘了檢查遍歷結(jié)束后棧是否為空這步導(dǎo)致(被誤判為合法。我還建議你在寫(xiě)完代碼后第一時(shí)間跑一遍這幾個(gè)用例(、)、()、(()、())。跑完這五個(gè)邊界問(wèn)題基本能暴露七八成。4.2 交叉嵌套誤區(qū)再回到那個(gè)經(jīng)典的([)]。用我們的棧算法跑一遍(入棧[入棧遇到)棧頂是[和)不匹配直接返回False。整個(gè)過(guò)程甚至沒(méi)走完整個(gè)字符串。這正是棧方案的威力交叉匹配在第一次出現(xiàn)張冠李戴時(shí)就會(huì)被攔截根本不需要等到最后。而計(jì)數(shù)法在這個(gè)用例上會(huì)完全失明。所以我在面試考這道題時(shí)特別喜歡把([)]作為追問(wèn)用例拋出去看候選人能不能頂住這一問(wèn)。如果你能主動(dòng)在代碼里展示對(duì)這個(gè)用例的處理并且說(shuō)明為什么它是非法的面試官對(duì)你是會(huì)有好感的。順便提一個(gè)變體([])是合法的([)]是非法的這兩個(gè)字符串長(zhǎng)得極為相似差的就是那一層嵌套關(guān)系。建議你把這兩個(gè)用例對(duì)照著在代碼上跑一跑直觀感受一下順序?qū)ㄌ?hào)匹配到底意味著什么。4.3 棧溢出與性能考量還有一種寫(xiě)法是用遞歸來(lái)處理括號(hào)匹配遞歸函數(shù)每次處理一個(gè)括號(hào)對(duì)遞歸深度等于嵌套深度。如果測(cè)試用例里給出一個(gè)幾千層嵌套的字符串比如(重復(fù) 5000 次再接 5000 個(gè))遞歸方案很容易觸發(fā)棧溢出。在 Python 里尤其明顯默認(rèn)遞歸深度限制大約在 1000 層稍微大一點(diǎn)就直接RecursionError。顯式棧方案就不會(huì)有這個(gè)問(wèn)題。因?yàn)闂Ｊ欠峙湓诙焉系膭?dòng)態(tài)結(jié)構(gòu)不受函數(shù)調(diào)用棧深度限制只要內(nèi)存夠幾萬(wàn)層嵌套也能處理。這也解釋了為什么算法題里遇到棧相關(guān)問(wèn)題時(shí)優(yōu)先寫(xiě)顯式棧而不是遞歸穩(wěn)定、可控、不依賴語(yǔ)言運(yùn)行時(shí)設(shè)置。雖然業(yè)務(wù)代碼里我們經(jīng)常追求遞歸的簡(jiǎn)潔但在這種深度可能很大的場(chǎng)景里顯式循環(huán)是更穩(wěn)妥的選擇。5. 常見(jiàn)錯(cuò)誤與調(diào)試實(shí)錄5.1 經(jīng)典錯(cuò)誤速查表我把平時(shí)見(jiàn)到的各種錯(cuò)誤集中整理成一張表刷題時(shí)可以直接對(duì)照自檢易錯(cuò)點(diǎn)典型輸入錯(cuò)誤后果正確做法棧為空時(shí)直接取棧頂)拋出索引越界或空棧異常先判空再取棧頂遍歷結(jié)束忘記檢查棧空(()誤把未閉合括號(hào)判為合法返回前檢查棧是否為空只統(tǒng)計(jì)括號(hào)數(shù)量不判斷順序([)]交叉括號(hào)被誤判為合法用棧維護(hù)順序信息棧頂匹配時(shí)只比較是左括號(hào)(]不同類型括號(hào)混配用哈希表做精確配對(duì)用Stack類實(shí)現(xiàn)任意不必要的性能開(kāi)銷用ArrayDeque誤把pairs鍵值方向?qū)懛?(匹配邏輯反了鍵是右括號(hào)值是左括號(hào)第五行和第六行看似小問(wèn)題但實(shí)際犯的人不少特別是從 C 轉(zhuǎn)到 Java 的人習(xí)慣了std::stack就順手寫(xiě)了Stack。算法題雖然不卡那點(diǎn)性能但這些細(xì)節(jié)能體現(xiàn)你對(duì)語(yǔ)言生態(tài)了解多少。5.2 實(shí)用調(diào)試技巧調(diào)試這道題我推薦兩個(gè)特別實(shí)用的方法。第一把棧的內(nèi)容打印出來(lái)。在每次入棧和出棧之后print(stack)尤其在處理復(fù)雜嵌套用例時(shí)肉眼看一下棧頂?shù)淖兓R上能定位是匹配邏輯錯(cuò)了還是彈出時(shí)機(jī)錯(cuò)了。我曾經(jīng)在處理三四種括號(hào)混合嵌套的用例時(shí)靠打印棧快速發(fā)現(xiàn)自己在遇到右括號(hào)時(shí)把pop放在了比較之前導(dǎo)致棧頂已經(jīng)被拿走自然比較什么都不對(duì)。這種 bug 光靠讀代碼很難抓打印一次立刻現(xiàn)形。第二準(zhǔn)備一組九宮格測(cè)試用例覆蓋所有情況。我自己固定跑這九組1. → 預(yù)期 true空串合法 2. () → 預(yù)期 true簡(jiǎn)單配對(duì) 3. (} → 預(yù)期 false類型不匹配 4. ({}) → 預(yù)期 true嵌套合法 5. ([)] → 預(yù)期 false交叉非法 6. {[]} → 預(yù)期 true多種嵌套合法 7. ((())) → 預(yù)期 true多層嵌套合法 8. (() → 預(yù)期 false左括號(hào)剩余 9. )( → 預(yù)期 false右括號(hào)開(kāi)頭任何實(shí)現(xiàn)如果過(guò)不了這九組都不算真正寫(xiě)完。它們涵蓋了空串、簡(jiǎn)單匹配、類型不匹配、嵌套合法、交叉非法、未閉合、順序錯(cuò)誤等所有場(chǎng)景。我還會(huì)順手在本地寫(xiě)一個(gè)小的驅(qū)動(dòng)器把這組用例和我的isValid函數(shù)綁在一起跑省去每次手動(dòng)輸入的麻煩。5.3 幾道延伸題目學(xué)完這道題有幾道題我強(qiáng)烈建議立刻去刷它們都是有效括號(hào)的直系后代。第一道是 LeetCode 22括號(hào)生成。它要求生成所有合法的括號(hào)組合核心是回溯加左右括號(hào)數(shù)量控制和棧的關(guān)系在于你要理解什么才算一個(gè)合法前綴。第二道是 LeetCode 32最長(zhǎng)有效括號(hào)。難度明顯上一個(gè)臺(tái)階需要?jiǎng)右?guī)或棧很考驗(yàn)綜合運(yùn)用能力。第三道是 LeetCode 678有效的括號(hào)字符串。它加入了通配符*可以用貪心或者雙棧解決思路極其巧妙能把你的思維從確定性匹配拉到概率性匹配。我的建議是先把第 20 題做透再按 22 → 32 → 678 的順序挑戰(zhàn)。這幾道題串下來(lái)你對(duì)棧模型的理解會(huì)有一個(gè)質(zhì)的飛躍。很多剛開(kāi)始刷題的人喜歡一個(gè)專題只做一道題就走其實(shí)最吃虧——因?yàn)橥粋€(gè)數(shù)據(jù)結(jié)構(gòu)在不同變體里展現(xiàn)出的特性才是真正需要花時(shí)間吸收的東西。我在實(shí)際面試和刷題過(guò)程中最深的一點(diǎn)體會(huì)是有效的括號(hào)這道題代碼量不到二十行但它是理解棧的一把鑰匙。無(wú)數(shù)后來(lái)讓我頭疼的題目——單調(diào)棧、表達(dá)式求值、函數(shù)調(diào)用棧模型、編譯原理里的括號(hào)語(yǔ)法分析——追根溯源都和這題背后的最近匹配思想相通。第一次寫(xiě)這道題時(shí)我也犯過(guò)只數(shù)左右括號(hào)的錯(cuò)被([)]狠狠教訓(xùn)過(guò)之后才真正理解了為什么括號(hào)匹配不只是數(shù)量問(wèn)題。如果你剛開(kāi)始刷題我建議你把這題做透多跑幾組邊界用例把棧的 push、pop、判空練成肌肉記憶。之后再遇到嵌套匹配類的問(wèn)題你會(huì)感謝這一道題打下的底子。