题目描述

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

示例 1：

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

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

输入：s = “”
输出：0

提示：

0 <= s.length <= 3 * 104
s[i] 为 ‘(‘ 或 ‘)’

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

算法2

设（ = 1，）= -1
有效括号相当于 所有 前缀和>=0 并且总和=0

((()) 这种情况，只会出现cnt>0,没有cnt=0的时候，会返回0.所以反着在计算一次

参考文献

C++ 代码

class Solution {
public:

    int work(string &s){
        int cnt = 0, start = 0, res = 0;
        for(int i=0; i<s.size(); ++i){
            if(s[i] == '(') ++cnt;
            else{
                --cnt;
                if(cnt < 0){
                    cnt = 0;
                    start = i+1;
                }
                else if(cnt == 0){
                    res = max(res, i - start + 1);
                }
            }
        }
        return res;
    }
    int longestValidParentheses(string s) {
        int res = 0;
        res = work(s);
        // cout<<res<<endl;
        int a = '(' - ')';
        reverse(s.begin(),s.end());
        for(auto &r : s){
            if(r == '(') r = ')';
            else  r = '(';
        }
        return max(res, work(s));
    }
};