该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

最长有效括号

题目背景

本题是括号匹配问题的经典进阶题型，在基础括号匹配的基础上，要求求解最长连续有效子串的长度。本题可通过栈、动态规划、双指针等多种方法求解，是考察数据结构与算法思维的经典题目。

题目描述

给定一个只包含字符 '(' 和 ')' 的字符串，请你找出其中最长的有效括号子串的长度。

有效括号子串定义为：格式正确且连续的括号子串。格式正确指每个左括号都有对应的右括号将其闭合，且括号嵌套顺序正确，例如 "(()())" 是格式正确的括号字符串。

输入格式

一行一个字符串 $s$，仅由字符 '(' 和 ')' 组成，字符串可以为空。

输出格式

一行一个整数，表示最长有效括号子串的长度。若不存在有效括号子串，输出 $0$。

样例 #1

样例输入 #1

(()

样例输出 #1

2

样例解释 #1

最长有效括号子串是 "()"，长度为 $2$。

样例 #2

样例输入 #2

)()())

样例输出 #2

4

样例解释 #2

最长有效括号子串是 "()()"，长度为 $4$。

样例 #3

样例输入 #3

样例输出 #3

0

样例解释 #3

输入为空字符串，不存在有效括号子串，输出 $0$。

样例 #4

样例输入 #4

(()())

样例输出 #4

6

样例解释 #4

整个字符串都是有效括号子串，长度为 $6$。

提示

数据范围与约定

• 对于 $100\%$ 的数据，保证字符串长度 $0 \le n \le 3 \times 10^4$。
• 字符串中仅包含字符 '(' 和 ')'。

算法提示

1. 暴力枚举法：枚举所有可能的子串，逐一检查是否为有效括号串。时间复杂度 $O(n^2)$，无法通过全部测试点。
2. 栈解法（推荐入门）：
   • 使用栈存储未匹配括号的下标，初始时向栈中压入 $-1$ 作为有效子串的起始基准。
   • 遍历字符串：遇到 '(' 时将其下标压入栈；遇到 ')' 时先弹出栈顶元素。
   • 若弹出后栈为空，说明当前右括号无法匹配，将当前下标压入栈作为新的基准；否则，当前下标与栈顶元素的差值即为以当前右括号结尾的有效子串长度，更新最大值。
   • 时间复杂度 $O(n)$，空间复杂度 $O(n)$。