一道LeetCode的多種解法

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

題目描述

給定一個只包含'('和')'的字符串，找出最長的包含有效括號的子串的長度。

示例 1:

輸入:"(()" 輸出:2 解釋:最長有效括號子串為"()"

示例 2:

輸入:")()())" 輸出:4 解釋:最長有效括號子串為"()()"

題目解析

解法一：棧

一開始看到這個題目，有點熟悉的感覺：相當(dāng)于是 LeetCode 第 20 題有效的括號的升級版。

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

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

對于這道題目，因為我們要求的是子串的長度，因此我們可以考慮在棧中保存index，這樣子我們不僅可以通過index找到對應(yīng)的括號，還可以借此來求長度，我們的思路可以分為下面幾步：

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

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

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

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

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

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

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

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

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

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

代碼實現(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()]=='('){ //配對的'('出棧 stack.pop(); //記錄長度 result=Math.max(result,i-stack.peek()); }else{//其他情況，直接將當(dāng)前位置入棧 stack.push(i); } } returnresult; }

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

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

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

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

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

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

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

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

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

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

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

代碼實現(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; } //前一個位置是')' //我們從當(dāng)前位置往左看，如果第一個沒有被匹配的位置是'(' //表明當(dāng)前位置是可以被匹配的 elseif(i-dp[i-1]-1>=0&&sArr[i-dp[i-1]-1]=='('){ //這里其實是dp[i]=i-(i-dp[i-1]-1)+1=dp[i-1]+2 //但是我們還需要考慮之前的答案，也就是dp[i-dp[i-1]-2] //首先判斷i-dp[i-1]-2是否越界 //如果沒有越界就將其加上 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; }

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

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

解法三：借助變量

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

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

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

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

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

代碼實現(xiàn)

//代碼來源：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; } }

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