type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给你一个只包含
'(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如
"(()())"。示例 1：
示例 2：
示例 3：
解法一：两次遍历（推荐）
- 从左到右遍历：用
l,r计数。遇到(->l+=1，遇到)->r+=1。 - 若
l == r，说明形成了一个有效段，更新答案max(ans, 2*r)。 - 若
r > l，右括号多了，不可能再补齐，本段作废，计数清零。
- 从右到左再遍历一遍（镜像）：
l == r时更新答案。- 若
l > r，左括号多了，计数清零；
两次双向遍历可覆盖如
"(()" 这类仅靠单向遍历无法判断的情况。 复杂度
- 时间：
O(n)（两趟线性）
- 空间：
O(1)（常数）
解法二：栈
在计算最长有效括号时，用公式：
长度 = i - stack[-1]。其中 i 是当前下标，stack[-1] 是最近一个“无效位置”或未匹配的左括号之前的位置。栈里存放下标，并在栈底维护一个最近一次不匹配位置的哨兵，初始为
-1。扫描字符串：
(：下标入栈。
)：弹栈；- 若栈空了，说明当前
)不能被匹配，把当前下标入栈当新的“无效边界”； - 否则， 用
i - stack[-1]更新答案。
例子：
- 字符串：
"()" - 初始栈：
[-1] - 扫描到
(：入栈 →[-1, 0] - 扫描到
)：弹出 →[-1] - 扫描结束，计算长度 =
1 - (-1) = 2
复杂度
- 时间：
O(n)
- 空间：
O(n)（最坏全是(）
解法三：动态规划
用
dp[i]记录 以当前位置 i 结尾 的最长有效括号的长度，并通过前面已经计算好的结果来“接续”或“扩展”新的匹配。有效括号串必须以
) 结尾。在动态规划里，只有遇到 ) 才能触发“匹配”逻辑，更新长度。- 直接匹配：当
s[i-1] == '('，那么s[i-1]和s[i]可以直接配对，长度就是以i-2结尾的结果加上 2， 即dp[i] = dp[i-2] + 2
- 接续匹配：如果前一个字符
s[i-1]也是)，需要看能否和更前面的(配对。如果s[j] =’('，找到匹配，就把前一段的有效长度接上。
其中，
j = i - dp[i-1] - 1 ， 因为位置 i 和 i-1 都是 ) ，说明在 i-1 之前有一段完整的有效括号，需要跳过这段有效括号长度dp[i-1] 去匹配它前一个字符。复杂度
- 时间：
O(n)
- 空间：
O(n)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-32-最长有效括号
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 25] K 个一组翻转链表
下一篇
[Leetcode 34] 在排序数组中查找元素的第一个和最后一个位置