32.最长有效括号 python

最长有效括号

题目
- 题目描述
- 示例 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