最长有效括号
- 题目
- 题目描述
- 示例 1：
- 示例 2：
- 示例 3：
- 提示：
- 题目链接
- 题解
- 算法步骤：
- python实现
- 解释：
- 提交结果
题目
题目描述
给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = “(()”
输出：2
解释：最长有效括号子串是 “()”
示例 2：
输入：s = “)()())”
输出：4
解释：最长有效括号子串是 “()()”
示例 3：
输入：s = “”
输出：0
提示：
0 <= s.length <= 3 * 104
s[i] 为 ‘(’ 或 ‘)’
题目链接
最长有效括号
题解
要解决这个问题，我们可以使用栈（stack）来帮助我们追踪括号匹配的情况。具体来说，栈可以帮助我们记住每一个未匹配的左括号的位置，当我们遇到一个右括号时，可以尝试与最近的未匹配的左括号进行匹配，并计算有效括号子串的长度。
此外，为了处理所有可能的有效括号子串，我们需要考虑从字符串的两端进行扫描。这是因为有些情况下，仅从左到右或仅从右到左的一次扫描无法覆盖所有的有效括号组合。例如，在字符串 ")(()())" 中，从左到右扫描会错过中间的 "()()" 有效子串；而从右到左扫描则能正确捕捉到这个情况。
下面是具体的算法实现：
算法步骤：
- 初始化变量：设置两个计数器
left和right分别记录左括号和右括号的数量，以及结果变量max_len来保存最长有效括号子串的长度。 - 从左向右扫描：遍历字符串，当遇到左括号时增加
left计数，遇到右括号时增加right计数。如果left和right相等，则更新max_len；如果right大于left，重置计数器。 - 从右向左扫描：同样地，重新遍历字符串但这次是从右往左，目的是为了捕捉那些在第一次扫描中被忽略的有效括号子串。这里需要交换
left和right的角色。 - 返回结果：最终返回
max_len。
这种方法的时间复杂度是 O(n)，因为每个字符最多被访问两次（一次从左到右，一次从右到左），空间复杂度是 O(1)，因为我们只用了常数级别的额外空间。
python实现
以下是 Python 实现代码：
def longestValidParentheses(s: str) -> int:left = right = max_len = 0# From left to rightfor char in s:if char == '(':left += 1elif char == ')':right += 1if left == right:max_len = max(max_len, 2 * right)elif right > left:left = right = 0left = right = 0# From right to leftfor char in reversed(s):if char == '(':left += 1elif char == ')':right += 1if left == right:max_len = max(max_len, 2 * left)elif left > right:left = right = 0return max_len
解释：
- 第一次扫描（从左到右）：这一步确保了我们可以找到所有以左括号开始的有效括号子串。
- 第二次扫描（从右到左）：这一步是为了补充第一次扫描中可能遗漏的情况，即那些以右括号结束的有效括号子串。
通过结合这两个方向的扫描，我们可以准确地找出最长的有效括号子串。
提交结果
