32. 最长有效括号

https://leetcode.cn/problems/longest-valid-parentheses/description/?show=1

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

两次遍历，贪心，对称性破缺

从左到右，检查每个左括号子串是否可成为一串有效括号，如果是，则计算长度，否则啥也不干。

从右到左，检查每个右括号子串是否可成为一串有效括号，如果是，则计算长度，否则啥也不干。

归并计算最大值。

对称性破缺，有效括号是成对出现的，这是一种对称，但是我们先让左括号地位比右括号大（即固定左括号，正常来说左右括号的个数是需要根据对方动态调整的，例如((())，如果左右括号对称的话，那么有效字符串的长度是4，但是目前我们要以左括号为主，所以有效字符串的长度是0），计算它的最长对称性，再让右括号的地位比左括号大，计算它的最长对称性，最后取最大值。

class Solution {
    public int longestValidParentheses(String s) {
        // 初始化左右括号计数器和最大长度
        int left = 0, right = 0, maxlength = 0;
        // 第一遍从左到右遍历字符串
        for (int i = 0; i < s.length(); i++) {
            // 遇到左括号，增加左括号计数
            if (s.charAt(i) == '(') {
                left++;
            } else {
                // 遇到右括号，增加右括号计数
                right++;
            }
            
            // 如果左右括号数相等，更新最大长度，注意要通过right计算，因为left可能大于right。
            // 注意right<left时不能计算！例如"()(()"，right=2，left=3，如果计算maxLength的话答案是4，但是答案应该是2。
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } 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) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left > right) {
                // 如果左括号数超过右括号数，重置计数器
                left = right = 0;
            }
        }
        
        // 返回最大有效括号长度
        return maxlength;
    }
}

• 时间复杂度： O(n)，其中 n 为字符串长度。我们只要正反遍历两边字符串即可。
• 空间复杂度： O(1)。我们只需要常数空间存放若干变量。

动态规划

计算与当前的右括号配对的左括号的索引

class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()]; // dp[i] 表示以下标 i 字符结尾的最长有效括号的长度
        
        // 注意从索引1开始遍历
        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) == '(') {
                    // 以((())为例，假设i指向第二个右括号，那么dp[i-1]就是以第一个右括号结尾的最长字符串的长度，即2，i-dp[i-1]-1就是以第一个右括号结尾的最长字符串的前一个字符，即第二个左括号，它是一个左括号，所以dp[i]（以第二个右括结尾的最长字符串的长度）就是dp[i-1]（以第一个右括号结尾的最长字符串的长度）+2（第二个左括号和第二个右括号）+dp[i-dp[i-1]-2]（以第一个左括号结尾的最长字符串的长度）。
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

• 时间复杂度：O(n)，其中 n 为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。
• 空间复杂度：O(n)。我们需要一个大小为 n 的 dp 数组。