思路:

• 两次线性扫描(每次扫描用双指针来找有小括号子串)
• 抓住有效括号的两条重要性质
• 有效括号的两个重要性质:
  1.如果把’(‘看作1,’)’看作’-1’，那么一个能构成有效括号的总和为0
  2.一个字符串能构成有效括号，那么任意顺序它都能构成有效括号
• 如果只从前扫描一遍的话无法保证得到正确答案(看wzc题解1)

时间复杂度(O(N))

class Solution {
    private int process(char[] chars){
        int n = chars.length;
        int ans = 0;
        int cnt = 0;
        for(int i = 0 , j = 0 ; i < n ; i++){
            //双指针找最长有效括号子串的长度
            if(chars[i] == '(')
                cnt++;
            else{
                cnt--;
                if(cnt < 0){
                    j = i + 1;
                    cnt = 0;
                }else if(cnt == 0){
                    ans = Math.max(i - j + 1,ans);
                }
            }
        }
        return ans;
    }

    public int longestValidParentheses(String s) {
        int ans = process(s.toCharArray());
        char[] reverse = new StringBuilder(s).reverse().toString().toCharArray();
        for(int i = 0 ; i < reverse.length ; i++)
            reverse[i] ^= 1;
        ans = Math.max(ans,process(reverse));
        return ans;
    }
}