32. 最长有效括号

难度：困难

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

解答：

class Solution {
    //动态规划
    //时间复杂度O(N), 空间复杂度O(N)
    public int longestValidParentheses(String s) {
        int maxAns = 0;
        int[] dp = new int[s.length()];
        for(int i = 1; i < s.length(); i++){
            if(s.charAt(i) == ')'){
                if(s.charAt(i - 1) == '('){
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }else if(i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '('){
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxAns = Math.max(dp[i], maxAns);
            }
        }
        return maxAns;
    }
}

class Solution {
    //栈
    //时间复杂度O(N), 空间复杂度O(N)
    public int longestValidParentheses(String s) {
        int maxAns = 0;
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    stack.push(i);
                }else{
                    maxAns = Math.max(maxAns, i - stack.peek());
                }
            }
        }
        return maxAns;
    }
}

class Solution {
    //双指针
    //时间复杂度O(N), 空间复杂度O(1)
    public int longestValidParentheses(String s) {
        int maxAns = 0;
        int left = 0;
        int right = 0;
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') left++;
            else right++;
            if(left == right) maxAns = Math.max(maxAns, right * 2);
            else if(right > left) left = right = 0;
        }
        left = right = 0;
        for(int i = s.length() - 1; i >= 0; i--){
            if(s.charAt(i) == '(') left++;
            else right++;
            if(left == right) maxAns = Math.max(maxAns, left * 2);
            else if(left > right) left = right = 0;
        }
        return maxAns;
    }
}

参考自：

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。