> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/dong-tai-gui-hua/32-zui-chang-you-xiao-kuo-hao.md).

# \[32]\[困难]\[动态规划]\[栈] 最长有效括号

## 题目描述

[32. 最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/)

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

示例 1:

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

示例 2:

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

## 解题思路

### 栈

思路参考: [最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/)

可以观察到, 导致只包含左右圆括号字符串整体不有效的原因有两种情况:

* 左侧左圆括号`(`过多, 右侧的右圆括号`)`只覆盖了一部分
* 左侧右圆括号`)`过多

对于第一种情况, 只要后面又出现右圆括号`)`, 就可以修复, 从而整体括号都有效. 但第二种情况, 一旦出现右圆括号`)`过多, 这个位置之前的部分就无法修复了. 而且判断右圆括号过多只需使用到当前字符为止的子串, 不需要后续信息.

使用栈结构来解题, 结合上面的特点, 我们希望:

* 遇到左圆括号`(`, 则将左圆括号的信息压入栈中
* 遇到右圆括号`)`
  * 如果能够找到相匹配的左圆括号`(`, 能够将这个左圆括号`(`的信息消去, 而且能够求得匹配的长度
  * 如果不能够匹配, 说明是后续子串左侧的过多字符, 应当留在栈中

另外可以发现, 最长有效括号的长度, 一定等于这个**有效序列最后一个字符的下标**, 减去**前面最后一个没有被匹配的字符的下标**, 如果有效序列从下标0开始, 认为最后一个没有匹配的下标为-1.

最后栈的解法如下:

* **首先在栈中压入一个`-1`表示最后一个没有被匹配的括号的下标**
* 对于遇到的每个左圆括号`(`, 将它的**下标**放入栈中
* 对于遇到的每个右圆括号`)`, **首先弹出栈顶元素**, 假设当前右括号能够匹配
  * 如果栈不为空, 认为匹配成功, 当前右括号的下标减去栈顶元素即为**以该右括号为结尾的最长有效括号的长度**. 因为栈顶元素已经弹出来, 此时在栈顶的不是所匹配的左括号下标
  * 如果栈为空, 说明当前的右括号没有找到匹配, 我们将其下标放入栈中来更新**最后一个没有被匹配的右括号的下标**

为什么栈的空与否能作为判断匹配成功的标志?

* 栈中首先压入了一个`-1`, 一开始就不是空的
* 如果能够匹配, 则对应的左括号下标已经被压入其中, 弹出的是该左括号的下标, 栈中一定还有最后一个没有被匹配的右括号的下标
* 在遇到右括号时, 首先将栈顶元素弹出, 当不匹配时, 再将该右括号的下标压入栈中, 代替原来下标, 成为新的最后一个没有被匹配的右括号的下标. 因此栈中**有且只有一个**最后一个没有被匹配的右括号的下标, 这也与我们的判断逻辑相符, 我们不再需要之前的信息, 滚动更新边界即可.
  * 而在遇到右括号时, 首先将栈顶元素弹出, 此时的栈就为空了
* 如果累计了大量的左括号, 栈中会有很多下标, 这时来一个有括号肯定是匹配的, 而此时的栈也不为空, 满足栈不空则匹配的逻辑

最后代码如下:

```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_len = 0

        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                stack.pop()
                if stack:
                    max_len = max(max_len, i - stack[-1])
                else:
                    stack.append(i)
        return max_len
```

### 动态规划

思路参考: [最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/)

首先定义状态$$dp\[i]$$表示以下标$$i$$字符结尾的最长有效括号的长度, 初始化时所有位置为0即可.

状态转移考虑如下:

* 下标$$i$$对应的字符若为左圆括号`(`, 肯定不是有效子串的结尾, $$dp\[i]$$保持为0
* 下标$$i$$对应的字符若为右圆括号`)`
  * 可能与左边紧邻的字符匹配, 若匹配, 长度在$$dp\[i - 2]$$的基础上加2, 即

      若$$s\[i]=\text{`)`}$$, 且$$s\[i-1]=\text{`(`}$$时, 状态转移方程为$$dp\[i]=dp\[i - 2]+2$$
  * 可能与左边非紧邻字符匹配, 将$$dp\[i - 1]$$指示的子串包裹起来, 此时有:

      $$s\[i]=\text{`)`}$$且$$s\[i-1]=\text{`)`}$$, 且$$s\[i-dp\[i-1]-1]=\text{`(`}$$, 状态转移方程为$$dp\[i]=dp\[i - 1]+2+dp\[i-dp\[i-1]-2]$$

总之, 注意匹配子串的串联关系.

```python
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        cache = [0] * len(s)
        max_len = 0
        for i, c in enumerate(s):
            if c == ')':
                if i - 1 >= 0:
                    if s[i - 1] == '(':
                        cache[i] = (cache[i - 2] if i - 2 >= 0 else 0) + 2
                    else:  # s[i - 1]为)
                        if i - cache[i - 1] - 1 >= 0 and s[i - cache[i - 1] - 1] == '(':
                            cache[i] = cache[i - 1] + 2 + (cache[i - cache[i - 1] - 2] if i - cache[i - 1] - 2 >= 0 else 0)
                max_len = max(max_len, cache[i])
        return max_len
```