📝 题目描述

题目链接：最长有效括号

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

子字符串 是字符串中连续的字符序列。

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

  • 0 <= s.length <= 3 * 10^4
  • s[i] 为 '(' 或 ')'

💡 解题思路

方法一：动态规划

我们定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。我们将 dp 数组全部初始化为 0 。显然有效的子串一定以 ) 结尾，因此我们可以知道以 ( 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解 ) 在 dp 数组中对应位置的值。

我们从前往后遍历字符串求解 dp 值，我们每次检查两个字符：

  1. 当 s[i] = ')' 且 s[i-1] = '(' 时，即字符串形如 “XXXXXX()”，我们可以推出：

    dp[i]=dp[i−2]+2.dp[i] = dp[i-2] + 2.

    这是因为末尾的 () 本身是一个有效括号子串，因此可以在此前有效括号子串长度的基础上增加 2。

  2. 当 s[i] = ')' 且 s[i-1] = ')' 时，也就是字符串形如 “XXXXXX))”。若

    s[i−dp[i−1]−1]=′(′,s[i-dp[i-1]-1] = '(',

    则有

    dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2.dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2.

第一种情况很好理解，这里重点解释一下第二种情况的公式原理。如果字符串形如 “XXXXXX))”，考虑如果倒数第二个 ‘)’ 是一个有效子字符串的一部分（记作 sub_s​），则对于最后一个 ‘)’，如果它是一个更长子字符串的一部分，那么它一定有一个对应的 ‘(’，且它的位置在倒数第二个 ‘)’ 所在的有效子字符串的前面（也就是 sub_s​ 的前面）。因此，如果子字符串 sub_s​ 的前面恰好是 ‘(’，那么我们就用 2 加上 sub_s​ 的长度（dp[i−1]dp[i−1]）去更新 dp[i]dp[i]。同时，我们也会把有效子串 “(sub_s​)” 之前的有效子串的长度也加上，也就是再加上 dp[i−dp[i−1]−2]dp[i−dp[i−1]−2]。

上面的推理逻辑略显复杂，其中有不少边界条件要注意，尤其是要避免 dp 数组下标小于零时造成的越界。

最后的答案即为 dp 数组中的最大值。

方法二：栈

首先，碰到 '('，就把它的位置信息入栈，很简单。关键在于碰到 ')'，那就要根据栈顶来分情况讨论了。

  1. 如果这时栈是空的，说明没有发现新的有效串，这个新来的 ')' 不可能找到对象的。那么当前 ')' 的下一个可能是下次能成功实现匹配的起始位（记为 next_start）。
  2. 如果这时栈不空，那么说明新来的 ')' 找到对象了，这时就 pop 出一个 '('，从 pop 出的 '(' 位置到当前必是有效的。
    • 如果这时栈空了，那说明找到了一个候选子串，从 next_start 到当前位置。
    • 如果这时栈不空，那也是找到了一个候选子串，从新栈顶的那个 '(' 之后的位置到当前位置。

为什么不只是从 pop 到当前呢? 因为从 next_start 到 pop 的位置必然也是有效的，肯定在之前都成双成对的走掉了。同样的道理，为什么是从栈顶到当前呢？也因为除了栈顶那个还没找到 ')' 配对，而它之后到 pop 的位置之间，肯定也都成双成对的走掉了。

方法三：双向遍历（无需额外空间）

在此方法中，我们利用两个计数器 left 和 right。首先，我们从左到右遍历字符串，对于遇到的每个 '('，我们增加 left 计数器，对于遇到的每个 ')' ，我们增加 right 计数器。每当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当 right 计数器比 left 计数器大时，我们将 left 和 right 计数器同时变回 0。

这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (()，这种时候最长有效括号是求不出来的。

解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：

  • 当 left 计数器比 right 计数器大时，我们将 left 和 right 计数器同时变回 0；
  • 当 left 计数器与 right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。

这样我们就能涵盖所有情况从而求解出答案。

🔧 代码实现

1、动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int longestValidParentheses(string s) {
        // 首先确定 s 的长度
        int n = s.size();
        // 创建dp数组
        vector<int> dp(n, 0);
        for (int i = 0; i < n; i++) {
            // 分情况讨论
            if ((s[i] == ')') && (i - 1 >= 0) && (s[i - 1] == '(')) {
                if ((i - 2 >= 0)) {
                    dp[i] = dp[i - 2] + 2;
                } else {
                    dp[i] = 2;
                }
            } else if ((s[i] == ')') && (i - 1 >= 0) && (s[i - 1] == ')')){
                if ((i - dp[i - 1] - 1 >= 0) && (s[i - dp[i - 1] - 1] == '(')) {
                    if ((i - dp[i - 1] - 2 >= 0)) {
                        dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                    } else {
                        dp[i] = dp[i - 1] + 2;
                    }
                }
            }
        }
        return n == 0 ? 0 : *max_element(dp.begin(), dp.end());
    }
};

2、栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> position_stk;
        int next_start = 0, res = INT_MIN;
        for (int i = 0; i < s.size(); i++) {
            // 为左括号，直接入栈 
            if (s[i] == '(') {
                position_stk.push(i);
            } else {
                // 右括号，分情况讨论
                if (position_stk.empty()){
                    // 栈为空，则规划新起点
                    next_start = i + 1;
                } else {
                    // 否则出栈
                    position_stk.pop();
                    if (position_stk.empty()){
                         // 栈为空，则计算新起点到目前位置的长度
                        res = max(i - next_start + 1, res);
                    } else {
                        // 否则计算栈顶到目前位置的长度
                        res = max(i - position_stk.top(), res);
                    }
                }
            }
        }
        return res == INT_MIN ? 0 : res;
    }
};

3、双向遍历（无需额外空间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    int longestValidParentheses(string s) {
        int left = 0, right = 0, res = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }

            if (left == right) {
                res = max(res, 2 * right);
            }
            if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for(int i = s.size() - 1; i >= 0; i--){
            if (s[i] == '(') {
                left++;
            } else {
                right++;
            }

            if (left == right) {
                res = max(res, 2 * left);
            }
            if (left > right) {
                left = right = 0;
            }
        }
        return res;
    }
};

📊 复杂度分析

1、动态规划

  • 时间复杂度：O(n)O(n)，其中 nn 为字符串的长度。我们只需遍历整个字符串一次，即可将 dpdp 数组求出来。
  • 空间复杂度：O(n)O(n)，我们需要一个大小为 nn 的 dpdp 数组。

2、栈

  • 时间复杂度：O(n)O(n)，nn 是给定字符串的长度。我们只需要遍历字符串一次即可。
  • 空间复杂度：O(n)O(n)，栈的大小在最坏情况下会达到 nn。

3、双向遍历（无需额外空间）

  • 时间复杂度：O(n)O(n)，其中 nn 为字符串长度，我们只要正反遍历两边字符串即可。
  • 空间复杂度：O(1)O(1)，我们只需要常数空间存放若干变量。

🎯 总结

  • 核心思想：栈的思想更通俗易懂，需要掌握。