题目内容

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

示例

示例 1：

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

示例 2：

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

示例 3：

输入：s = “”
输出：0

提示

1、0 <= s.length <= 3 * 10^4
2、s[i] 为 ‘(‘ 或 ‘)’

题解

本题是lc第22题的类型题，考察括号匹配的问题。首先，把推论继续复习一下：

1、在任意有效的前缀中，左括号数量一定大于等于右括号数量

2、在整个有效的括号匹配区间中，左括号数量等于右括号数量

接下来，有如下思考。

1、首先，我们要理解一下所求的有效子串一定不会跨越两个区间。也就是说，当找到不符合有效规则的子串末尾字符位置的时候，前面的子串不可能与后面可能的有效子串拼接在一起。

2、基于1，我们可以知道，可以通过分段的思想考虑，即通过推论的两点规则，去判断当前的子串区间是否符合规则，如果符合规则，继续判断，直到不符合规则为止，记录当前子串的长度；如果不符合规则，那么从下一个位置重新开始寻找符合要求的子串，重复上述步骤。

3、每次找到子串就和已经找到的子串的最大子串长度进行比较，始终维护有效子串的全局最大值。最后返回最大值即可。

具体，请看代码。

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        //分段的思想，要求的子串不可能存在跨越两个区间。
        //另外，为了能够有效匹配，一定有左右括号数量相等，任意前缀中，左括号数量大于等于右括号数量。
        stack<int> stk;
        int res = 0;
        for(int i = 0, start = -1; i < s.size(); i++){
            //用start描述当前字符的前一个位置
            if(s[i] == '(') stk.push(i);//如果当前字符是左括号，则压栈。
            else{
                if(stk.size()){ //首先判断栈是否为空，不为空执行以下操作。
                    stk.pop(); //将栈头元素弹出
                    if(stk.size()){
                        res = max(res, i - stk.top()); //根据推论，当前段的最大长度就是i到栈头元素的长度。然后求出全局最大。
                    }else{
                        res = max(res, i - start);//因为栈空掉了  因此可以从头开始取
                    }
                }else{
                    start = i;//如果是右括号，则更新start。
                }
            }
        }
        return res;
    }
};