最长有效括号

## 1 题目

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

**示例 1：**

```txt
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
```

**示例 2：**

```txt
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
```

**示例 3：**

```txt
输入：s = ""
输出：0
```

**提示：**

* 0 <= s.length <= 3 * 104
* s[i] 为 '(' 或 ')'

## 2 解题思路

### 2.1 动态规划

#### 2.1.1 问题解析

1. 对于这种**最值型**题目一般采用**动态规划**的方法来求解。
2. 动态规划题目的分析分为以下 4 个步骤：
   1. **确定状态**：
      1. **研究最优策略的最后一步**。
      2. **化为子问题**。
   2. **转移方程**：
      1. **根据子问题定义得到**。
   3. **初始条件和边界情况**。
   4. **计算顺序**。
3. 首先，我们定义一个 $dp$ 数组，其中 $dp[i]$**表示以下标为 $i$ 的字符结尾的最长有效子字符串的长度**。
4. 然后进行动态规划的求解：
   1. **确定状态**：
      1. 对于最优的策略，一定有最后一个元素 $s[i]$，所以，我们先看第 $i$ 个位置，这个位置的元素 $s[i]$ 有两种情况：
         1. $s[i] = '('$：这时 $s[i]$**无法和其之前的元素组成有效的括号对**，所以 $dp[i] = 0$。
         2. $s[i] = ')'$：这时，**需要看其前面一个元素来判断是否为有效括号对**：
            1. $s[i - 1] = '('$：即 $s[i]$**和 $s[i - 1]$ 组成一对有效括号**，**有效括号长度新增 2**，此时以 $i$**位置的字符结尾的最长有效括号长度为以 $(i - 2)$ 位置的字符结尾的最长有效括号长度加 2**，我们**无需知道 $(i - 2)$ 位置的字符是否可以组成有序括号对**，此时有：

$$
               dp[i] = dp[i - 2] + 2
               $$

![截屏 2020-04-17 下午 4.30.46.png](/media/202107/2021-07-20_2159340.25846779094837236.png)
            2. $s[i - 1] = ')'$：这种情况下，如果**前面有和 $s[i]$ 组成有效括号对的字符**，即形如 $((...)) $，这样的话，就**要求 $s[i - 1]$ 位置必然是有效的括号对**，否则 $s[i]$**无法和前面对字符组成有效括号对**，这时，我们只需**找到和 $s[i]$ 配对的字符的位置**（$i - dp[i - 1] - 1$），并**判断其是否可以和 $s[i]$ 配对**即可：

1. 如果 $s[i - dp[i - 1] - 1] = '('$，即 $s[i - dp[i -1] - 1]$**可以和 $s[i]$ 配对**，则**以 $s[i]$ 结尾的最长有序括号长度为以 $s[i - 1]$ 为结尾的最长有序括号长度加 2**，此时有：

$$
                  dp[i] = dp[i - 1] + 2
                  $$

需要注意的是，$s[i - dp[i - 1] - 1]$ 和 $s[i]$ 组成了有序括号对，这将是**一段独立的有序括号对**，如果**之前的子序列是形如 $(...)$ 这种序列**，那么**当前位置的最长有序括号对的长度还需加上这一段**，即：

$$
                  dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
                  $$

![截屏 2020-04-17 下午 4.26.34.png](/media/202107/2021-07-20_2215560.0730175812392132.png)
   2. **子问题**：
      1. 根据上面的分析，我们得到了如下**两个计算公式**：

$$
         dp[i] = dp[i - 1] + 2
         $$

$$
         dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 1] + 2
         $$
      2. 那么，求 $dp[i]$ 就变成了**求 $dp[i - 1]$**、**$dp[i - 2]$**、**$dp[i - dp[i - 1] - 1]$ 的子问题**。
      3. 这样状态也明确了：**设 $dp$ 数组**，**其中第 $i$ 个元素表示以下标为 $i$ 的字符结尾的最长有效字符串的长度**。
   3. **转移方程**：
      1. **子问题明确后**，**转移方程直接由子问题得到**：

```java
         if (s.charAt(i) == '(') {
             dp[i] = 0
         }
         if (s.charAt(i) == ')') {
             if (s.charAt(i - 1) == '(') {
                 dp[i] = dp[i - 2] + 2 // 要保证 i - 2 >= 0
               }
             if (s.charAt(i - 1) == ')' && s[i - dp[i - 1] - 1] == '(') {
                 dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 // 要保证 i - dp[i - 1] - 2 >= 0
               }
         }
         ```
   4. **初始条件和边界情况**：
      1. **初始条件**：$dp[i] = 0$。
      2. **边界情况**：**需要保证计算过程中 $i - 2 >= 0$ 和 $i - dp[i - 1] - 2 >= 0$**。
   5. **计算顺序**：
      1. **无论第一个字符是什么**，**都有**$dp[0] = 0$。
      2. **然后依次计算**$dp[1]、dp[2],...,dp[n - 1]$。
      3. **最后结果是 $max(dp[i])$**。

#### 2.1.2 参考代码

```java
/**
 * 32. 最长有效括号（版本 1：动态规划）
 *
 * @param s 字符串
 * @return 字符串中最长有效括号子串的长度
 */
public int longestValidParenthesesV1(String s) {
    int m = s.length();
    //  dp 数组，其中 dp[i] 表示以 s.charAt(i) 结尾的最长有效括号子串的长度
    int[] dp = new int[m + 1];
    int res = 0;

for (int i = 1; i < m; i++) {
        if (s.charAt(i - 1) == '(' && s.charAt(i) == ')') {
            //  第 i - 1 个元素为 (，第 i 个元素为 )，即第 i - 1 个元素和第 i 个元素可以组成一个有序括号，则 dp[i] = dp[i - 2] + 2
            dp[i] = (i - 2 >= 0 ? dp[i - 2] : 0) + 2;
        } else if (s.charAt(i - 1) == ')' && s.charAt(i) == ')') {
            //  第 i - 1 个元素为 )，第 i 个元素为 )
            if (i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                //  如果 s.charAt(i - dp[i - 1] - 1) 为 (，即该元素和 s.charAt(i) 配对，则 dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2，其中 s.charAt(i - dp[i - 1] - 2) 为与 s.charAt(i) 配对的前一个元素
                dp[i] = dp[i - 1] + 2;
                if (i - dp[i - 1] - 2 >= 0) {
                    dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                }
            }
        }
        res = Math.max(res, dp[i]);
    }

//  返回最终结果
    return res;
}
```

### 2.2 栈

#### 2.2.1 问题分析

1. 对于这种**符号匹配**的题目，我们一般可以采用**栈**的方法来求解。
2. 具体做法是**我们始终保持栈底元素为当前已遍历过的元素中最后一个没有被匹配的右括号的下标**，这样的做法**主要是考虑了边界条件的处理**，**栈里其他元素维护左括号的下标**：
   1. **对于遇到的每个 `(`**，我们**将他的下标放入栈中**。
   2. **对于遇到的每个 `)`**，我们**先弹出栈顶元素表示匹配了当前右括号**：
      1. 如果**栈为空**，说明**当前的右括号为没有被匹配的右括号**，我们**将其下标放入栈中来更新我们之前提到的最后一个没有被匹配的右括号的下标**。
      2. 如果**栈不为空**，**当前右括号的下标减去栈顶元素即为以该括号为结尾的最长有效括号的长度**。
3. 然后我们**从前往后遍历字符串并更新答案即可**。
4. 需要注意的是，**如果一开始栈为空**，**第一个字符为左括号的时候**，**我们会将其放入栈中**，这样就**不满足提及的最后一个没有被匹配的右括号的下标**，**为了保持统一**，我们**在一开始的时候往栈中放入一个值为-1 的元素**。
5. 具体演示动画可参考[ 最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution)。

#### 2.2.2 参考代码

```java
/**
 * 32. 最长有效括号（版本 2：栈）
 *
 * @param s 字符串
 * @return 字符串中最长有效括号子串的长度
 */
public int longestValidParenthesesV2(String s) {
    int m = s.length();
    //  栈底元素始终为当前已经遍历过的元素中 最后一个没有被匹配的右括号的下标
    Stack<Integer> stack = new Stack<>();
    int maxLength = 0;

//  如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样栈就不满足栈底元素始终为当前已遍历过的元素中 最后一个没有被匹配的右括号的下标，为了保持统一，我们在一开始的时候往栈中放入一个值为 -1 的元素
    stack.push(-1);
    for (int i = 0; i < m; i++) {
        char item = s.charAt(i);

if (item == '(') {
            //  如果当前遍历的元素为 (，则把当前元素的下标放入栈中
            stack.push(i);
        } else if (item == ')') {
            //  当前遍历的元素为 )
            if (!stack.empty()) {
                //  如果栈不为空，则将栈顶元素弹出
                stack.pop();
            }

if (stack.size() == 0) {
                //  如果栈为空，则把当前元素的下标放入栈中
                stack.push(i);
            } else {
                //  如果栈不为空，则 当前遍历元素的下标 减去 栈顶元素 即为以该右括号为结尾的最长有效括号的长度
                maxLength = Math.max(maxLength, i - stack.peek());
            }
        }
    }

//  返回结果
    return maxLength;
}
```

## 3 参考文献

1. [32. 最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses)。
2. [最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution)。
3. [动态规划思路详解（c++）——32.最长有效括号](https://leetcode-cn.com/problems/longest-valid-parentheses/solution/dong-tai-gui-hua-si-lu-xiang-jie-c-by-zhanganan042)。