32. 最长有效括号

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

方法一: 栈

栈的思路还是比较绕的。

定义1：一个合法括号序列的任意前缀左括号数量>=右括号的数量

定义2：一个恰好不合法的括号序列是一个以右括号结尾，恰好右括号数量 > 左括号数量的序列。必定为奇数长度。恰好不合法的括号序列如果除去结尾一个或者多个右括号，就是合法的括号序列。

比如说:

序列 (()))，是一个恰好不合法的序列。因为末位的右括号明显溢出，但是去掉结尾，又是一个合法的括号序列。

定义2为什么很重要？是因为这是一个在一个括号序列里划分的好办法。我们可以在括号序列里用该定义进行分段，然后对每段分别进行讨论。

为什么可以这么划分是由于一个很重要的性质：一段合法的括号序列不会交错两个不同的恰好不合法序列的区间。在此之后不会有另外一个合法序列用到了该括号序列的任何括号了。

可以使用反证法来考虑这个问题。假设有一个合法序列横跨了两个恰好不合法合法的括号序列。那么该合法序列的前缀必然有左括号的数量大于等于右括号数量的性质。但是和一个恰好不合法的括号序列满足的性质（末位的后缀部分的右括号数量一定严格大于左括号数量）互相矛盾。

对于每个区间，我们做以下处理。

1. 用栈记录括号的下标，遍历到右括号的时候，对长度最大值进行更新。

2. 特殊情况：如果栈变空了 ，那说明整个区间是合法区间。可以全部取。因此我们需要记录每个起点，或者起点前一个位置。

class Solution {
public:
    int longestValidParentheses(string s) {    
        stack<int> stk;
        int start = -1;
        int res = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') stk.push(i);
            else {
                if (!stk.empty()) { 
                    stk.pop(); // 将栈顶元素进行匹配
                    if (stk.empty()) { // 如果当前栈为空，说明该区间整个都是合法的。
                        res = max(res,i - start);
                    } else { // 如果栈不为空，更新当前长度即可。
                        res = max(res, i - stk.top() );
                    }
                } else {
                    start = i; // 重置区间起点。
                }
            }
        }
        return res;     
    }
};

时间复杂度$O(n)$，每个元素只会进出栈一次。

空间复杂度$O(n)$，使用了栈。

方法二: 两次遍历

遍历第一次：不断统计左括号和右括号的数量。如果左括号和右括号相等，统计最大结果。如果右括号在一个点大于了右括号，说明我们到了一个新的区间。本质上和方法一还是一样的。

遍历第二次：倒着遍历是必要的，因为可能存在左括号数量一致大于右括号的情况。倒着一边就可以避免。思路很简单，但是比较难想到。

坑点：注意倒过来遍历的时候，l和r清零的条件是左括号数量大于了右括号数量。

class Solution {
public:
    int longestValidParentheses(string s) {
        int l = 0, r = 0;
        int res = 0;
        for (auto& c : s) {
            if (c == ')') r++;
            else l++;
            if (l == r) res = max(res, l + r);
            if (r > l) l = 0, r = 0;
        }
        l = 0, r = 0;
        for (int i = (int)s.size() - 1; i >= 0; i--) {
            char c = s[i];
            if (c == ')') r++;
            else l++;
            if (l == r) res = max(res, l + r);
            if (l > r) l = r = 0;
        }
        return res;
    }
};