> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/32.longest-valid-parentheses.md).

# 0032. 最长有效括号

### 题目地址(32. 最长有效括号)

<https://leetcode-cn.com/problems/longest-valid-parentheses/>

### 题目描述

```
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

```

### 前置知识

* 动态规划

### 暴力（超时）

### 公司

* 阿里
* 腾讯
* 百度
* 字节

#### 思路

符合直觉的做法是：分别计算以 i 开头的 最长有效括号（i 从 0 到 n - 1·），从中取出最大的即可。

#### 代码

代码支持： Python

```py
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(N^2)$
* 空间复杂度：$O(1)$

### 栈

#### 思路

主要思路和常规的括号解法一样，遇到'('入栈，遇到')'出栈，并计算两个括号之间的长度。 因为这个题存在非法括号对的情况且求是合法括号对的最大长度 所以有两个注意点是:

1. **栈中存的是符号的下标**
2. **当栈为空时且当前扫描到的符号是')'时，需要将这个符号入栈作为分割符**
3. 栈中初始化一个 -1，作为**分割符**

#### 代码

* 语言支持: Python, javascript, CPP

javascript code:

```js
// 用栈来解
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:

```py

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
```

CPP Code:

```cpp
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == ')' && st.top() != -1 && s[st.top()] == '(') {
                st.pop();
                ans = max(ans, i - st.top());
            } else st.push(i);
        }
        return ans;
    }
};
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$

### O(1) 空间

#### 思路

我们可以采用解法一中的计数方法。

* 从左到右遍历一次，并分别记录左右括号的数量 left 和 right。
* 如果 right > left ，说明截止上次可以匹配的点到当前点这一段无法匹配，重置 left 和 right 为 0
* 如果 right == left, 此时可以匹配，此时有效括号长度为 left + right，我们获得一个局部最优解。如果其比全局最优解大，我们更新全局最优解

值得注意的是，对形如 `(((()` 这样的，更新全局最优解的逻辑永远无法执行。一种方式是再从右往左遍历一次即可，具体看代码。

> 类似的思想有哨兵元素，虚拟节点。只不过本题无法采用这种方法。

#### 代码

代码支持：Java，Python3, CPP

Java Code:

```java
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;
    }
}
```

Python3 Code:

```py
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
```

CPP Code:

```cpp
class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, ans = 0, N = s.size();
        for (int i = 0; i < N; ++i) {
            left += s[i] == '(';
            right += s[i] == ')';
            if (left == right) ans = max(ans, left + right);
            else if (right > left) left = right = 0;
        }
        left = 0, right = 0;
        for (int i = N - 1; i >= 0; --i) {
            left += s[i] == '(';
            right += s[i] == ')';
            if (left == right) ans = max(ans, left + right);
            else if (left > right) left = right = 0;
        }
        return ans;
    }
};
```

### 动态规划

#### 思路

所有的动态规划问题, 首先需要解决的就是如何寻找合适的子问题. 该题需要我们找到最长的有效括号对, 我们首先想到的就是定义**dp\[i]为前 i 个字符串的最长有效括号对长度**, 但是随后我们会发现, 这样的定义, 我们无法找到 dp\[i]和 dp\[i-1]的任何关系. 所以, 我们需要重新找一个新的定义: 定义**dp\[i]为以第 i 个字符结尾的最长有效括号对长度**. 然后, 我们通过下面这个例子找一下 dp\[i]和 dp\[i-1]之间的关系.

```python
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]**&#x4E2A;字符是配对的, 则 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. 以下为图解: ![32.longest-valid-parentheses](https://p.ipic.vip/u0te4a.jpg)

#### 代码

代码支持：Python3， CPP

Python3 Code:

```py
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
```

CPP Code:

```cpp
class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> dp(s.size() + 1, 0);
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') continue;
            int start = i - dp[i] - 1;
            if (start >= 0 && s[start] == '(')
                dp[i + 1] = dp[i] + 2 + dp[start];
            ans = max(ans, dp[i + 1]);
        }
        return ans;
    }
};
```

**复杂度分析**

* 时间复杂度：$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](/leetcode-solution/easy/20.valid-parentheses.md)

### 扩展

1. 如果判断的不仅仅只有'('和')', 还有'\[', ']', '{'和'}', 该怎么办?
2. 如果输出的不是长度, 而是任意一个最长有效括号对的字符串, 该怎么办?

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/8hx4j5.jpg)