最长有效括号

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

子串

的长度。

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：s = ""
输出：0

提示：

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

f[i]表示以s.charAt(i)为结尾的最长有效括号个数。

  • 如果s.charAt(i)=='(',f[i]=0,因为有效括号必须以右括号结尾
  • 如果s.charAt(i)==')'
    • 如果s.charAt(i-1)=='(',说明左边紧邻的就能匹配上，f[i]=f[i-2]+2,f[i-2]就是左括号左边的最大数量
    • 如果s.charAt(i-1)==')',检查和s.charAt(i-1)这个右括号匹配的左括号的左边是否为左括号，如果是：加上中间的有效括号个数和左边的最长有效括号数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n < 2)
            return 0;
        int[] f = new int[n];
        int max = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    f[i] = (i - 2 >= 0 ? f[i - 2] : 0) + 2;
                    // ()((()))
                    // 	 012345
                } else if (i - f[i - 1] - 1 >= 0 && s.charAt(i - f[i - 1] - 1) == '(') {
                    f[i] = f[i - 1] + 2 + (i - f[i - 1] - 2 >= 0 ? f[i - f[i - 1] - 2] : 0);
                }
            }
            max = Math.max(max,f[i]);
        }
        return max;
    }
}