0032. 最長有效括號 · ttttt

# 0032. 最長有效括號 ## 題目地址(32. 最長有效括號) <https://leetcode-cn.com/problems/longest-valid-parentheses/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個只包含 '(' 和 ')' 的字符串，找出最長的包含有效括號的子串的長度。示例 1: 輸入: "(()" 輸出: 2 解釋: 最長有效括號子串為 "()" 示例 2: 輸入: ")()())" 輸出: 4 解釋: 最長有效括號子串為 "()()" ``` ``` ## 前置知識 - 動態規劃 ## 暴力（超時） ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ### 思路符合直覺的做法是：分別計算以 i 開頭的最長有效括號（i 從 0 到 n - 1·），從中取出最大的即可。 ### 代碼代碼支持： Python ``` <pre class="calibre18">``` class Solution: def longestValidParentheses(self, s: str) -> int: n = len(s) ans = 0 def validCnt(start): # cnt 為 ) 的數量減去 ( 的數量 cnt = 0 ans = 0 for i in range(start, n): if s[i] == '(': cnt += 1 if s[i] == ')': cnt -= 1 if cnt < 0: return i - start if cnt == 0: ans = max(ans, i - start + 1) return ans for i in range(n): ans = max(ans, validCnt(i)) return ans ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N^2)O(N2) - 空間復雜度：O(1)O(1)O(1) ## 棧 ### 思路主要思路和常規的括號解法一樣，遇到'('入棧，遇到')'出棧，并計算兩個括號之間的長度。因為這個題存在非法括號對的情況且求是合法括號對的最大長度所以有兩個注意點是: 1. **棧中存的是符號的下標** 2. **當棧為空時且當前掃描到的符號是')'時，需要將這個符號入棧作為分割符** 3. 棧中初始化一個 -1，作為**分割符** ### 代碼 - 語言支持: Python, javascript javascript code: ``` <pre class="calibre18">``` // 用棧來解 var longestValidParentheses = function (s) { let stack = new Array(); let longest = 0; stack.push(-1); for (let i = 0; i < s.length; i++) { if (s[i] === "(") { stack.push(i); } else { stack.pop(); if (stack.length === 0) { stack.push(i); } else { longest = Math.max(longest, i - stack[stack.length - 1]); } } } return longest; }; ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution: def longestValidParentheses(self, s: str) -> int: if not s: return 0 res = 0 stack = [-1] for i in range(len(s)): if s[i] == "(": stack.append(i) else: stack.pop() if not stack: stack.append(i) else: res = max(res, i - stack[-1]) return res ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## O(1) 空間 ### 思路我們可以采用解法一中的計數方法。 - 從左到右遍歷一次，并分別記錄左右括號的數量 left 和 right。 - 如果 right > left ，說明截止上次可以匹配的點到當前點這一段無法匹配，重置 left 和 right 為 0 - 如果 right == left, 此時可以匹配，此時有效括號長度為 left + right，我們獲得一個局部最優解。如果其比全局最優解大，我們更新全局最優解值得注意的是，對形如 `(((()` 這樣的，更新全局最優解的邏輯永遠無法執行。一種方式是再從右往左遍歷一次即可，具體看代碼。 > 類似的思想有哨兵元素，虛擬節點。只不過本題無法采用這種方法。 ### 代碼代碼支持：Java，Python ``` <pre class="calibre18">``` public class Solution { public int longestValidParentheses(String s) { int left = 0, right = 0, maxlength = 0; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, left + right); } if (right > left) { left = right = 0; } } left = right = 0; for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '(') { left++; } else { right++; } if (left == right) { maxlength = Math.max(maxlength, left + right); } if (left > right) { left = right = 0; } } return maxlength; } } ``` ``` ``` <pre class="calibre18">``` class Solution: def longestValidParentheses(self, s: str) -> int: ans = l = r = 0 for c in s: if c == '(': l += 1 else: r += 1 if l == r: ans = max(ans, l + r) if r > l: l = r = 0 l = r = 0 for c in s[::-1]: if c == '(': l += 1 else: r += 1 if l == r: ans = max(ans, l + r) if r < l: l = r = 0 return ans ``` ``` ## 動態規劃 ### 思路所有的動態規劃問題, 首先需要解決的就是如何尋找合適的子問題. 該題需要我們找到最長的有效括號對, 我們首先想到的就是定義**dp\[i\]為前 i 個字符串的最長有效括號對長度**, 但是隨后我們會發現, 這樣的定義, 我們無法找到 dp\[i\]和 dp\[i-1\]的任何關系. 所以, 我們需要重新找一個新的定義: 定義**dp\[i\]為以第 i 個字符結尾的最長有效括號對長度**. 然后, 我們通過下面這個例子找一下 dp\[i\]和 dp\[i-1\]之間的關系. ``` <pre class="calibre18">``` s = '(())())' ``` ``` 從上面的例子我們可以觀察出一下幾點結論(**描述中 i 為圖中的 dp 數組的下標, 對應 s 的下標應為 i-1, 第 i 個字符的 i 從 1 開始**). 1. base case: 空字符串的最長有效括號對長度肯定為 0, 即: dp\[0\] = 0; 2. s 的第**1**個字符結尾的最長有效括號對長度為 0, s 的第**2**個字符結尾的最長有效括號對長度也為 0, 這個時候我們可以得出結論: 最長有效括號對不可能以'('結尾, 即: dp\[1\] = d\[2\] = 0; 3. 當 i 等于 3 時, 我們可以看出 dp\[2\]=0, dp\[3\]=2, 因為第 2 個字符(**s\[1\]**)和第 3 個字符(**s\[2\]**)是配對的; 當 i 等于 4 時, 我們可以看出 dp\[3\]=2, dp\[4\]=4, 因為我們配對的是第 1 個字符(**s\[0\]**)和第 4 個字符(**s\[3\]**); 因此, 我們可以得出結論: 如果第**i**個字符和第**i-1-dp\[i-1\]**個字符是配對的, 則 dp\[i\] = dp\[i-1\] + 2, 其中: i-1-dp\[i-1\] >= 1, 因為第 0 個字符沒有任何意義; 4. 根據第 3 條規則來計算的話, 我們發現 dp\[5\]=0, dp\[6\]=2, 但是顯然, dp\[6\]應該為 6 才對, 但是我們發現可以將"(())"和"()"進行拼接, 即: dp\[i\] += dp\[i-dp\[i\]\], 即: dp\[6\] = 2 + dp\[6-2\] = 2 + dp\[4\] = 6 根據以上規則, 我們求解 dp 數組的結果為: \[0, 0, 0, 2, 4, 0, 6, 0\], 其中最長有效括號對的長度為 6. 以下為圖解: ![](https://img.kancloud.cn/38/15/3815532606043d7960729cac46e832ff_923x443.jpg) ### 代碼 Python Code: ``` <pre class="calibre18">``` class Solution: def longestValidParentheses(self, s: str) -> int: mlen = 0 slen = len(s) dp = [0] * (slen + 1) for i in range(1, len(s) + 1): # 有效的括號對不可能會以'('結尾的 if s[i - 1] == '(': continue left_paren = i - 2 - dp[i - 1] if left_paren >= 0 and s[left_paren] == '(': dp[i] = dp[i - 1] + 2 # 拼接有效括號對 if dp[i - dp[i]]: dp[i] += dp[i - dp[i]] # 更新最大有效擴對長度 if dp[i] > mlen: mlen = dp[i] return mlen ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ### 關鍵點解析 1. 第 3 點特征, 需要檢查的字符是 s\[i-1\]和 s\[i-2-dp\[i-1\]\], 根據定義可知: i-1 >= dp\[i-1\], 但是 i-2 不一定大于 dp\[i-1\], 因此, 需要檢查越界; 2. 第 4 點特征最容易遺漏, 還有就是不需要檢查越界, 因為根據定義可知: i >= dp\[i\], 所以 dp\[i-dp\[i\]\]的邊界情況是 dp\[0\]; ## 相關題目 - [20.valid-parentheses](20.valid-parentheses.html) ## 擴展 1. 如果判斷的不僅僅只有'('和')', 還有'\[', '\]', '{'和'}', 該怎么辦? 2. 如果輸出的不是長度, 而是任意一個最長有效括號對的字符串, 該怎么辦? 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)