题目描述

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

样例

示例 1：

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

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

输入：s = ""
输出：0
 

提示：

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

算法

(枚举) $O(n)$

思路：把每一段不匹配的落单括号下标统计上， 然后根据落单下标的间隔距离来求长度。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.empty()) return 0;
        int i = 0, j = s.size() - 1;
        while(i < s.size() && s[i] == ')') i ++;
        while(j >= 0 && s[j] == '(') j --;
        s = s.substr(i, j - i + 1);

        stack<int> stk, idx;

        //单独拿一个出来存储下标，一个push值，一个push下标
        for(int i = 0; i < s.size(); i++){
            if(stk.size() && s[i] == ')' && stk.top() == '(') stk.pop(), idx.pop();
            else stk.push(s[i]), idx.push(i);
        }
        int res = 0;
        int last = s.size();
        while(idx.size()){
            int t = idx.top();
            idx.pop();

            res = max(res, last - t - 1);
            last = t;
        }
        res = max(res, last);
        return res;
    }
};