题目

类型：Stack

难度：困难

解题思路

利用两个计数器 left 和 right 。

1、首先，从左到右遍历字符串，对于遇到的每个 (，增加 left 计数器，对于遇到的每个) ，增加 right 计数器。

2、每当 left 计数器与right 计数器相等时，计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。

3、当 right 计数器比 left 计数器大时，将 left 和 right 计数器同时变回 0。

4、每次当右括号数量多于左括号数量的时候之前的字符都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。解决的方法就是，需要从右往左遍历用类似的方法计算，只是这个时候判断条件反了过来

• 当left 计数器比right 计数器大时，将 left 和 right 计数器同时变回 0
• 当 left 计数器与 right 计数器相等时，计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串
  这样就能涵盖所有情况从而求解出答案。

代码

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++;
            }
            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;
    }
}