最长有效括号

给你一个只包含 '(' 和 ')' 的字符串 s。

请你找出最长有效括号子串的长度。

有效括号子串必须满足：

• 格式正确
• 连续
• 左右括号能够正确匹配

例如，"(()())" 是格式正确的括号字符串。

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

解法一（栈）：

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.push(i);
            }
            else
            {
                st.pop();

                if (st.empty())
                {
                    st.push(i);
                }
                else
                {
                    ans = max(ans, i - st.top());
                }
            }
        }

        return ans;
    }
};

解法二（动态规划）：

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n, 0);

        int ans = 0;

        for (int i = 1; i < n; i++)
        {
            if (s[i] == ')')
            {
                if (s[i - 1] == '(')
                {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                else
                {
                    int left = i - dp[i - 1] - 1;

                    if (left >= 0 && s[left] == '(')
                    {
                        dp[i] = dp[i - 1] + 2 + (left >= 1 ? dp[left - 1] : 0);
                    }
                }

                ans = max(ans, dp[i]);
            }
        }

        return ans;
    }
};

解法三（正反遍历计数）：

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        int left = 0;
        int right = 0;

        for (int i = 0; i < s.size(); i++)
        {
            if (s[i] == '(')
            {
                left++;
            }
            else
            {
                right++;
            }

            if (left == right)
            {
                ans = max(ans, 2 * right);
            }
            else if (right > left)
            {
                left = 0;
                right = 0;
            }
        }

        left = 0;
        right = 0;

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

            if (left == right)
            {
                ans = max(ans, 2 * left);
            }
            else if (left > right)
            {
                left = 0;
                right = 0;
            }
        }

        return ans;
    }
};

核心思想

这题要求的是最长有效括号子串，而且子串必须连续。

直接想法是枚举所有子串，再判断每个子串是否合法。

但字符串长度最多是 3 * 10^4，枚举子串会超时。

我们需要在一次或少数几次遍历中，快速判断当前位置能形成多长的有效括号。

这题最关键的观察是：

有效括号子串的边界，通常由“无法匹配的位置”分隔开。

也就是说，一个多余的右括号 ')' 会让它左边和右边不可能连成同一个有效子串。

栈解法就是利用这一点：

• 栈中保存还没有匹配的括号下标
• 栈底保存最近一个无法匹配的位置
• 当当前位置 i 能形成有效子串时，长度就是 i - st.top()

解法一：栈

栈中保存的是下标，而不是括号字符。

原因是我们最终要求的是长度。

初始时先放入：

st.push(-1);

这个 -1 可以理解为“有效子串开始之前的位置”。

例如字符串一开始就是：

()

当遍历到下标 1 的 ')' 时，如果栈顶是 -1，长度就是：

1 - (-1) = 2

正好表示整个 "()" 的长度。

栈的更新逻辑

当遇到 '(' 时，把它的下标入栈：

st.push(i);

它表示当前左括号还没有被匹配。

当遇到 ')' 时，先弹出栈顶：

st.pop();

这个弹出动作有两种含义：

• 如果栈顶是一个 '(' 的下标，表示用当前 ')' 匹配它
• 如果栈顶是一个无法匹配的位置，表示当前 ')' 也无法匹配，需要更新边界

弹出后，如果栈为空，说明当前 ')' 没有左括号可以匹配。

于是把当前下标作为新的边界：

st.push(i);

如果栈不为空，说明当前 ')' 成功参与了一个有效括号子串。

此时从 st.top() + 1 到 i 这一段都是有效的，长度是：

i - st.top()

所以更新答案：

ans = max(ans, i - st.top());

解法二：动态规划

动态规划的思路是固定结尾位置。

定义：

dp[i] 表示以 s[i] 结尾的最长有效括号子串长度。

如果 s[i] == '('，它不可能作为有效括号子串的结尾，所以：

dp[i] = 0

只有当 s[i] == ')' 时，才有可能形成有效括号。

动态规划递推公式

当 s[i] == ')' 时，分两种情况。

1. 前一个字符是 '('

形如：

...()

此时最后两个字符能组成一对括号。

再接上 i - 2 位置结尾的有效括号长度：

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

如果 i < 2，前面没有内容，就只加 2。

代码中写成：

dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;

2. 前一个字符是 ')'

形如：

...))

这时要看前面已经形成的一段有效括号之前，是否还有一个 '(' 可以和当前 ')' 匹配。

以 i - 1 结尾的有效括号长度是：

dp[i - 1]

所以这段有效括号的左边界是：

i - dp[i - 1]

它前一个位置是：

left = i - dp[i - 1] - 1

如果：

left >= 0 && s[left] == '('

说明 s[left] 可以和当前 s[i] 匹配。

此时新的有效长度包括三部分：

• 中间已有的有效括号：dp[i - 1]
• 新匹配的一对括号：2
• 更前面可能紧挨着的一段有效括号：dp[left - 1]

所以：

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

代码中要注意 left - 1 是否越界：

dp[i] = dp[i - 1] + 2 + (left >= 1 ? dp[left - 1] : 0);

解法三：正反遍历计数

还可以用两个计数器：

• left：当前段中 '(' 的数量
• right：当前段中 ')' 的数量

从左往右遍历时：

• 如果 left == right，说明当前段括号数量平衡，可以更新答案
• 如果 right > left，说明右括号过多，这一段不可能再成为有效括号子串，需要清零重新开始

但是只从左往右有一个问题：

(() 

这里 left 一直多于 right，不会触发 right > left，但其中确实有有效子串 "()"。

所以还需要从右往左再遍历一次。

从右往左时，如果：

left > right

说明左括号过多，需要清零。

这样两次遍历合起来，就能覆盖两类失衡情况。

边界情况

如果 s 是空字符串：

s = ""

没有任何非空有效括号子串，答案是 0。

栈解法中，循环不会执行，返回初始的 ans = 0。

动态规划中，dp 是空数组，循环不会执行，也返回 0。

正反遍历计数中，两次循环都不会产生有效长度，返回 0。

如果字符串全是 '(' 或全是 ')'，也无法形成有效括号子串。

答案同样是 0。

正确性证明

我们证明：栈解法和动态规划解法都能返回最长有效括号子串的长度。

结论 1：栈中始终保存还没有被匹配的位置和最近的无效边界

初始时，栈中放入 -1，表示字符串开始前的边界。

遇到 '(' 时，它暂时没有匹配的右括号，所以把下标入栈。

遇到 ')' 时，弹出栈顶。

如果弹出的是某个 '(' 的下标，说明当前 ')' 成功匹配了它。

如果弹出后栈为空，说明当前 ')' 无法匹配任何左括号，于是把当前下标作为新的无效边界。

因此栈顶始终表示当前有效子串左边最近的阻断位置。

结论 2：栈解法计算出的 i - st.top() 是以 i 结尾的最长有效括号长度

当遍历到 i 且 s[i] == ')' 时，如果弹出后栈不为空，说明当前右括号已经成功匹配。

此时栈顶下标之前的位置，要么是未匹配的左括号，要么是无法匹配的右括号边界。

从 st.top() + 1 到 i 之间的括号都已经正确匹配。

所以这一段是一个有效括号子串，长度为：

i - st.top()

由于 st.top() 是离 i 最近的阻断位置，再往左就无法继续组成以 i 结尾的有效子串。

因此这个长度就是以 i 结尾的最长有效括号长度。

结论 3：动态规划中，dp[i] 正确表示以 s[i] 结尾的最长有效括号长度

如果 s[i] == '('，有效括号不可能以左括号结尾，所以 dp[i] = 0 正确。

如果 s[i] == ')' 且 s[i - 1] == '('，最后两个字符组成一对括号。

此时能接上的只有 i - 2 位置结尾的有效括号，所以：

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

如果 s[i] == ')' 且 s[i - 1] == ')'，那么必须找到前一段有效括号左边的那个字符。

只有当它是 '(' 时，才能和当前 ')' 匹配，并把三段连接起来。

这正是公式：

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

所以动态规划转移覆盖了所有以 s[i] 结尾的有效括号情况，也不会加入不合法的括号。

结论 4：答案取所有位置结尾的最大值是正确的

任意一个有效括号子串，一定有一个结束位置 i。

如果它以 i 结尾，那么它的长度不会超过该位置能得到的最长有效括号长度。

无论使用栈解法还是动态规划解法，算法都会在每个可能结尾位置更新答案。

所以最终得到的 ans 就是所有有效括号子串长度的最大值。

得出结论

由结论 1 和结论 2 可知，栈解法能正确计算每个位置结尾的有效长度。

由结论 3 可知，动态规划解法的状态转移正确。

由结论 4 可知，最终答案取最大值正确。

因此算法正确。

举例理解

以：

s = ")()())"

为例，看栈解法。

初始：

stack = [-1]

遍历过程：

最终答案是：

4

对应最长有效括号子串：

"()()"

复杂度分析

解法一

每个下标最多入栈一次、出栈一次。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

解法二

遍历字符串一次，dp 数组长度为 n。

• 时间复杂度：O(n)
• 空间复杂度：O(n)

解法三

正向遍历一次，反向遍历一次。

只使用常数个计数变量。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

如果只需要长度，解法三空间最优；如果想更直观地理解匹配边界，解法一更推荐。