题目描述

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

样例

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

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

输入：s = ""
输出：0

限制

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

算法1

(两次线性扫描、贪心) $O(n)$

1. 假设当前从前到后统计合法括号子串，令 ( 的权值为 1，) 的权值为 -1。首先记录 start 为某个起点，则在 i 向后移动的过程中，若当前 [start,i] 区间和等于 0，该字符串是合法的，更新答案；若区间和大于 0，则说明目前缺少右括号，可以不修改 start；若区间和小于 0，则说明区间已经不合法了，需要修正 start 为 i+1。初始时 start 从 0 开始即可。
2. 可是对于 ...((((合法)((( 这种情况，以上算法不能够准确捕捉到最长的合法子串，此时我们逆向考虑，将以上过程反向，从后向前统计，即可处理所有的情况。

时间复杂度

• 两次线性扫描，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        int start = 0, val = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(') val++;
            else val--;
            if (val < 0) {
                val = 0;
                start = i + 1;
            }
            else if (val == 0)
                ans = max(ans, i - start + 1);
        }

        start = n - 1; val = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == ')') val++;
            else val--;
            if (val < 0) {
                val = 0;
                start = i - 1;
            }
            else if (val == 0)
                ans = max(ans, start - i + 1);
        }
        return ans;
    }
};

算法2

(动态规划) $O(n)$

1. 设 $f(i)$ 为以 $i$ 为结尾的最长合法子串。
2. 初始时，$f(0) = 0$。
3. 转移时，我们仅考虑当前字符是 ) 的时候。如果上一个字符是 (，即 ...() 结尾的情况，则 $f(i) = f(i - 1) + 2$。
4. 如果上一个字符是 )，即 ...)) 的情况，则我们通过上一个字符的动规结果，判断是否能匹配末尾的 )。判断 s[i - f(i - 1) - 1] 是 (，即 ...((合法))，则可以转移 $f(i) = f(i - 1) + 2 + f(i - f(i - 1) - 2)$。
5. 最终答案为动规数组中的最大值。

时间复杂度

• 状态数为 $O(n)$，每次转移有两种情况，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 空间的记录状态。

C++ 代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        vector<int> f(n, 0);
        for (int i = 1; i < n; i++)
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    if (i >= 2) f[i] = f[i - 2] + 2;
                    else f[i] = 2;
                } else {
                    if (i - f[i - 1] - 1 >= 0 && s[i - f[i - 1] - 1] == '(')
                        if (i - f[i - 1] - 2 >= 0)
                            f[i] = f[i - 1] + 2 + f[i - f[i - 1] - 2];
                        else
                            f[i] = f[i - 1] + 2;
                }
            }

        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = max(ans, f[i]);

        return ans;
    }
};

算法3

(栈) $O(n)$

1. 用栈维护当前待匹配的左括号的位置。同时用 start 记录一个新的可能合法的子串的起始位置。初始设为 0。
2. 遇到左括号，当前位置进栈。
3. 遇到右括号，如果当前栈不空，则当前栈顶出栈。出栈后，如果栈为空，则更新答案 i - start + 1；否则更新答案 i - st.top()。
4. 遇到右括号且当前栈为空，则当前的 start 开始的子串不再可能为合法子串了，下一个合法子串的起始位置是 i + 1，更新 start = i + 1。

时间复杂度

• 每个位置遍历一次，最多进栈一次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 空间的维护栈。

C++ 代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.length();
        stack<int> st;

        int start = 0, ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '(')
                st.push(i);
            else {
                if (!st.empty()) {
                    st.pop();
                    if (st.empty())
                        ans = max(ans, i - start + 1);
                    else
                        ans = max(ans, i - st.top());
                } else {
                    start = i + 1;
                }
            }
        }

        return ans;
    }
};