32.最长有效括号(困难)

题目链接

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

解答

class Solution {
    public int longestValidParentheses(String s) {
        // 分析：有效括号串中，一定是先出现"("，再出现对应的")"。只要一个子串中所有先出现的"("都能找到匹配的")",则有效子串存在
        // 1.遍历字符串，找到"("字符，如果i下标处字符为")"，则跳过。注意，如果存在最长有效括号字符串，不一定是从这个字符开始的。
        // 因为一个有效字符串后如果是一个")"，有效字符串在")"处结束，原字符串在此")"后可能存在更长的有效括号字符串
        // 2.如果i开头能获取到有效字符串，更新结果值，并从该有效字符串结尾位置下一字符往后遍历
        // 如果i开头字符串的"("字符多于")"，则
        int firstHalfNums = 0;      // 用来记录待匹配")"的"("括号数量
        int i = 0;
        int res = 0;
        int len = 0;
        // 寻找以"("开头的字符，作为有效子串的起点
        while (i < s.length()) {
            if (s.charAt(i++) == '(') {
                int j = i - 1;
                int end = 0;
                boolean resHasUpdated = false;
                // 找到了"("字符，从该字符寻找最长有效括号字符串
                while (j < s.length()) {
                    if ((firstHalfNums += s.charAt(j++) == '(' ? 1 : -1) < 0) break;
                    len++;
                    // 每当firstHalfNums为0时，说明当前字符串中"("与")"数量相匹配，更新一次结果值
                    if (firstHalfNums == 0) {
                        res = Math.max(res, len);
                        end = j - 1;
                        resHasUpdated = true;
                    }
                }
                len = 0;
                firstHalfNums = 0;
                if (resHasUpdated) i = end + 1;
            }
        }
        return res;
    }
}