Leetcode 最长连续有效括号

这道题有这几个关键点：

1. 输入只可能是圆括号 ‘(’ 或 ‘)’
2. 寻找连续的最长有效括号

算法思想：

我们通过两次扫描字符串来找出最长的有效括号子串：一次从 左到右 扫描，另一次从 右到左 扫描。这两次扫描可以分别解决不同的括号不平衡情况（多余的左括号 '(' 和多余的右括号 ')'）。

1. 第一次遍历：从左到右扫描

• 在这个过程中，我们维护两个计数器 left 和 right，分别记录当前左括号 '(' 和右括号 ')' 的数量。
• 每当遇到左括号时，我们将 left 加一；遇到右括号时，我们将 right 加一。
• 如果 left == right，说明当前子串是有效的，我们可以计算出有效括号的长度，并更新最大长度 maxLength。
• 如果 right > left，说明右括号多于左括号，此时不可能形成有效的括号序列，所以我们将 left 和 right 重置为0，重新开始计数。

2. 第二次遍历：从右到左扫描

• 在第一次遍历中，我们只能解决从左到右扫描时的情况，但有些时候字符串中可能存在多余的左括号（即 '(' 多于 ')'），这在从左到右的扫描中无法完全处理。
• 因此，我们再从右到左进行一次遍历，使用相同的计数器 left 和 right。
• 这次遍历时，当 left > right 时（即左括号多于右括号），我们将计数器重置为0，因为此时不可能形成有效的括号序列。

通过两次遍历，算法可以有效处理两种可能的不平衡情况，从而找到最长的有效括号子串。

时间复杂度：

该算法的时间复杂度是 O(n)，其中 n 是字符串的长度。因为我们只需要对字符串进行两次遍历，所以整体复杂度是线性的。

这道题的算法之所以和使用栈进行括号匹配不同的一个重要原因是这道题目的输入只可能是"(“或”)“，而不会出现”[“,”]“,”{“,”}"

为什么这道题可以不用栈？

因为题目只包含两种括号 "(" 和 ")"，不需要担心嵌套关系，也不需要区分括号的种类。通过计数左右括号的数量，我们就可以判断出某个子串是否为有效的括号子串。

• 当左右括号的数量相等时，说明子串是有效的。
• 当右括号数量超过左括号时，当前子串不可能再有效，需要重新开始计数。

从左往右遍历时，只要一个子串的起始元素不是右括号")“，那么只要if (left == right)就可以断定形成了有效括号。
从右往左遍历时，只要一个子串的起始元素不是左括号”("，那么只要if (left == right)就可以断定形成了有效括号。

class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxLength = 0;
        //第一遍, 从左往右遍历, 只要一个子串的起始元素不是右括号")"，
        // 那么只要if (left == right)就可以断定形成了有效括号
        for(int i = 0; i < s.length(); ++i) {
            if(s.charAt(i) == '(') {
                left++;
            } else if(s.charAt(i) == ')'){
                right++;
            }

            if(left == right) {
                maxLength = Math.max(maxLength, 2 * left);
            } else if(right > left) {
            //如果第一个元素是右括号, 例如')(', 此时 right = 1 > left = 0,这里避免了')('这种误认
            //left和right都置 0 相当于更新了连续有效括号检测的起点
                left = 0;
                right = 0;
            }
        }

        left = 0;
        right = 0;
        //第二遍, 从右往左遍历
        for(int i = s.length() - 1; i >= 0; i--) {
            if(s.charAt(i) == '(') {
                left++;
            } else if(s.charAt(i) == ')'){
                right++;
            }

            if(left == right) {
                maxLength = Math.max(maxLength, 2 * left);
            }else if(left > right) {
                left = 0;
                right = 0;
            }
        }
        return maxLength;
    }
}