贪心算法判定对称条件。

题目链接-来源：力扣（LeetCode）

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

示例 1：

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

思路：

我们可以遍历每个字符。分别记录正括号和反括号的数量 left 和 right。当两个数字相等时，即可判断整个子串有效，更新最大子串长度。而当右括号的数量较大时，我们就可以将两个数字置 0，因为多余的右括号出现在最右时，左侧的子串已经不能构成合法的字符串。
这种考虑有个瑕疵，就是当左侧有很多多余的左括号时，我们的 right 永远小于 left，即使遍历到字符串末尾也无法统计出有效子串长度。此时我们只需反向遍历字符串，将前面的判断规则镜像处理，以左括号数量超越右括号为重置条件。

时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int longestValidParentheses(String s) {
        int len = s.length();
        int left = 0, right = 0;
        int maxCount = 0;
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            
            if (left != 0 && left == right) {
                maxCount = Integer.max(maxCount, left << 1);
            }
            if (right > left) {
                right = 0;
                left = 0;
            }
        }
        
        left = 0;
        right = 0;
        
        for (int i = len - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            
            
            if (left != 0 && left == right) {
                maxCount = Integer.max(maxCount, left << 1);
            }
            if (left > right) {
                right = 0;
                left = 0;
            }
        }
    
        return maxCount;
    }
}