Leetcode 最新上線了手機(jī)版 APP，今天蹲坑的時(shí)候隨手翻了一道題，一道和棧有關(guān)的題目，大概知道了解題思路，就點(diǎn)開(kāi)了題解準(zhǔn)備看看別人是如何寫(xiě)代碼的，沒(méi)想到最后一種解法讓我感覺(jué)自己的智商受到了碾壓。

題目描述

給定一個(gè)只包含'('和')'的字符串，找出最長(zhǎng)的包含有效括號(hào)的子串的長(zhǎng)度。

示例 1:

輸入:"(()" 輸出:2 解釋:最長(zhǎng)有效括號(hào)子串為"()"

示例 2:

輸入:")()())" 輸出:4 解釋:最長(zhǎng)有效括號(hào)子串為"()()"

題目解析

解法一：棧

一開(kāi)始看到這個(gè)題目，有點(diǎn)熟悉的感覺(jué)：相當(dāng)于是 LeetCode 第 20 題有效的括號(hào)的升級(jí)版。

想到這立馬嘗試借助棧這個(gè)數(shù)據(jù)結(jié)構(gòu)去解決。

括號(hào)相關(guān)的問(wèn)題首先可以嘗試使用棧這個(gè)數(shù)據(jù)結(jié)構(gòu)去解決，至于原因，想一想應(yīng)該不難理解，如果進(jìn)來(lái)一個(gè)右括號(hào)，也就是 ')'，它會(huì)和之前最后一次遍歷到的左括號(hào)匹配，棧的先進(jìn)后出的特性保證了這一要求。

對(duì)于這道題目，因?yàn)槲覀円蟮氖亲哟拈L(zhǎng)度，因此我們可以考慮在棧中保存index，這樣子我們不僅可以通過(guò)index找到對(duì)應(yīng)的括號(hào)，還可以借此來(lái)求長(zhǎng)度，我們的思路可以分為下面幾步：

1、從左到右遍歷輸入的字符串

2、如果遇到的是'('，意味著這并不能和前面遍歷過(guò)的部分組成合法答案，此時(shí)我們只需要把當(dāng)前index入棧即可

3、如果遇到的是')'，這時(shí)我們就要看棧頂保存的元素了，這里就會(huì)有幾種情況：

棧頂保存的是'('，表示當(dāng)前元素和棧頂元素可以配對(duì)，這個(gè)時(shí)候我們需要把棧頂元素彈出棧，記錄答案則記錄當(dāng)前index和彈出配對(duì)元素后的新棧頂index之間的距離，這個(gè)地方是重點(diǎn)，如果不理解，你可以思考下面兩個(gè)例子：

"((()()" "((())"

棧頂保存的是')'，如果是這種情況，表示前面沒(méi)有可配對(duì)的 '('，我們此時(shí)還是需要把當(dāng)前index入棧，原因是

我們確定距離需要知道邊界，如果不理解，還是有兩個(gè)例子供你參考：

"))(())" "())()()"

棧是空的，當(dāng)然在第一種情況中，你彈出棧頂元素后也會(huì)使得棧變空，為了避免這種情況，我們可以在最開(kāi)始的時(shí)候推一個(gè)-1入棧，這樣可以節(jié)省我們的判斷次數(shù)，并且當(dāng)棧中的沒(méi)有元素的時(shí)候，我們也可以用這個(gè)-1來(lái)計(jì)算當(dāng)前子串的長(zhǎng)度，你可以參考下面這兩個(gè)例子：

"()" "()(())"

代碼實(shí)現(xiàn)

publicintlongestValidParentheses(Strings){ if(s==null||s.length()==0){ return0; } intn=s.length(); char[]sArr=s.toCharArray(); Stackstack=newStack<>(); intresult=0; //-1入棧用于處理邊界條件 stack.push(-1); for(inti=0;i1表示棧不為空，而且我們必須保證棧頂元素是'(' if(sArr[i]==')'&&stack.size()>1&&sArr[stack.peek()]=='('){ //配對(duì)的'('出棧 stack.pop(); //記錄長(zhǎng)度 result=Math.max(result,i-stack.peek()); }else{//其他情況，直接將當(dāng)前位置入棧 stack.push(i); } } returnresult; }

解法二：動(dòng)態(tài)規(guī)劃

如果用棧來(lái)解決的話，這道題思路差不多就是這樣。考慮到前不久一直聊動(dòng)態(tài)規(guī)劃，于是試了一下用把它歸納到序列型動(dòng)態(tài)規(guī)劃來(lái)求解。

動(dòng)態(tài)規(guī)劃之空間優(yōu)化與總結(jié)回顧

我們可以定義dp[i] 表示的是 str[0…i] 的答案，思路其實(shí)和前面很類似：

1、從左到右遍歷輸入的字符串

2、如果遇到的是 '('，意味著這并不能和前面遍歷過(guò)的部分組成合法答案，因?yàn)?dp 狀態(tài)數(shù)組中記錄的是答案，這個(gè)時(shí)候說(shuō)明 dp[i] = 0，也就是不用做任何記錄

3、如果遇到的是 ')'，這時(shí)我們還是需要往前看：

如果 str[i - 1] 是 '('，那么 dp[i] = dp[i - 2] + 2

如果 str[i - 1] 是 ')'，這表示 str[i - 1] 已經(jīng)配對(duì)了，因此我們還要繼續(xù)往前看，從當(dāng)前位置往左，看第一個(gè)沒(méi)有被配對(duì)的 '('，怎么找這個(gè)位置呢，這里我們就可以利用 dp[i - 1] 這個(gè)信息，dp[i - 1] 表示的是之前匹配的長(zhǎng)度，那么 ：

i - dp[i - 1] - 1表示的就是從當(dāng)前位置往左，第一個(gè)沒(méi)有被配對(duì)的位置

如果位置 i 和 位置 i - dp[i - 1] - 1 配對(duì)后，我們可以看看當(dāng)前的序列是否可以和之前匹配的序列鏈接起來(lái)，也就是加上 dp[i - dp[i - 1] - 2]

代碼實(shí)現(xiàn)

publicintlongestValidParentheses(Strings){ if(s==null||s.length()==0){ return0; } intn=s.length(); char[]sArr=s.toCharArray(); int[]dp=newint[n]; intresult=0; for(inti=1;i=2?dp[i-2]:0)+2; } //前一個(gè)位置是')' //我們從當(dāng)前位置往左看，如果第一個(gè)沒(méi)有被匹配的位置是'(' //表明當(dāng)前位置是可以被匹配的 elseif(i-dp[i-1]-1>=0&&sArr[i-dp[i-1]-1]=='('){ //這里其實(shí)是dp[i]=i-(i-dp[i-1]-1)+1=dp[i-1]+2 //但是我們還需要考慮之前的答案，也就是dp[i-dp[i-1]-2] //首先判斷i-dp[i-1]-2是否越界 //如果沒(méi)有越界就將其加上 dp[i]=dp[i-1]+2; if(i-dp[i-1]>=2){ dp[i]+=dp[i-dp[i-1]-2]; } } result=Math.max(result,dp[i]); } } returnresult; }

兩種方法時(shí)空復(fù)雜度都是 O(n)，解法也有相似之處，只是說(shuō)切題點(diǎn)不一樣。

正當(dāng)我美滋滋時(shí)，突然看到另外一種解法，讓我感覺(jué)自己的智商受到了碾壓：不需要額外的空間，空間復(fù)雜度是 O(1)！

解法三：借助變量

使用了兩個(gè)變量 Left 和 Right，分別用來(lái)記錄到當(dāng)前位置時(shí)左括號(hào)和右括號(hào)的出現(xiàn)次數(shù)。

當(dāng)遇到左括號(hào)時(shí)，Left 自增 1，右括號(hào)時(shí) Right 自增1。

對(duì)于最長(zhǎng)有效的括號(hào)的子串，一定是左括號(hào)等于右括號(hào)的情況，此時(shí)就可以更新結(jié)果 res 了，一旦右括號(hào)數(shù)量超過(guò)左括號(hào)數(shù)量了，說(shuō)明當(dāng)前位置不能組成合法括號(hào)子串，Left 和 Right 重置為 0。

但是對(duì)于這種情況 "(()" 時(shí)，在遍歷結(jié)束時(shí)左右子括號(hào)數(shù)都不相等，此時(shí)沒(méi)法更新結(jié)果 res，但其實(shí)正確答案是 2，怎么處理這種情況呢？

答案是再反向遍歷一遍，采取類似的機(jī)制，稍有不同的是此時(shí)若 Left 大于 Right 了，則重置 0，這樣就可以涵蓋所有情況。

代碼實(shí)現(xiàn)

//代碼來(lái)源：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/ publicclassSolution{ publicintlongestValidParentheses(Strings){ intleft=0,right=0,maxlength=0; for(inti=0;i=left){ left=right=0; } } left=right=0; for(inti=s.length()-1;i>=0;i--){ if(s.charAt(i)=='('){ left++; }else{ right++; } if(left==right){ maxlength=Math.max(maxlength,2*left); }elseif(left>=right){ left=right=0; } } returnmaxlength; } }

事實(shí)上，我在利用解法一求解完這道題目后還怡然自得，認(rèn)為這道題目最簡(jiǎn)單的解法就是借助棧這種數(shù)據(jù)結(jié)構(gòu)，沒(méi)想到還有解法三這么巧妙的解法。。。