最长有效括号
Longest Valid Parentheses
给定只含 '(' 和 ')' 的字符串，求最长的有效（括号正确配对）子串长度。
在力扣中练习题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
解题思路
一维 DP · 以右括号结尾
只讨论以 s[i-1] 结尾的有效段，分“相邻配对”和“跨段配对”
枚举所有子串再逐段检查括号匹配是 O(n³)。把状态定义在结尾上：dp[i] 表示以 s[i-1] 结尾的最长有效括号长度。
如果 s[i-1] 是 '('，不可能有以它结尾的有效串，dp[i] = 0。如果它是 ')'，分两种：
- 前一个字符正好是
'('：这两个字符配对，接到 dp[i-2] 后面，dp[i] = dp[i-2] + 2； - 前一个字符也是
')'：先跨过 dp[i-1] 这段有效串，再看它前面的字符是不是'('。若是，dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]。
自拟主例 s = "(()())"。中间的 () 让 dp[3]=2、dp[5]=4；最后的 ) 跨过长度 4 的段，匹配开头的 (，再把更前面的 dp[0] 拼上，得到 6。
dp[i]：以 s[i-1] 结尾的最长有效括号长度；s = "(()())"
写入0
dp[4]=0s[3..4] = "()"，直接接在 dp[3] 后面：dp[5] = 2 + 2 = 4。
- dp[i]
- 4
dp[i]：以 s[i-1] 结尾的最长有效括号长度；s = "(()())"
dp[3] = 24✓写入4
dp[5]=dp[3] + 22 + 2=4边界：dp[0]=dp[1]=0。答案取所有 dp 的最大值，因为最长有效段不一定在末尾。时间 O(n)，空间 O(n)。
易错点
- dp 只开 n 个：dp[n] 对应整个串，需要 n+1 的空间。
- 跨段时忘记加 dp[i-dp[i-1]-2]：前面的有效段会被丢掉，答案偏小。
- 下标 i-dp[i-1]-2 可能为负，必须先判断 >= 0 再访问 s。
栈 · 未匹配位置
栈里存还没配对的左括号下标，栈底存最后一个断点
时间同为 O(n)，栈版本不需要推导转移方程；空间 O(n)，但更容易直接还原最长段的起止位置。
从左到右扫描，用栈保存“还没被匹配的位置”：
- 遇到
'('：把下标入栈； - 遇到
')'：先弹出一个位置。如果栈空了，说明这个右括号多余，把它的下标压入栈当新断点；如果栈不空，当前下标减去栈顶，就是以当前位置结尾的有效段长度。
栈底始终是最后一个没匹配上的位置。例如 "(()())"，扫描到最后一个 ) 时，栈顶是开头的 ( 的前一个断点 -1，长度就是 5 - (-1) = 6。
时间 O(n)，空间 O(n)。
- 1栈中先压入 -1，表示起点前的断点。
- 2遇到 '(' 压入下标。
- 3遇到 ')' 先弹出；栈空则把当前下标压入当断点。
- 4栈不空时用 i - 栈顶更新答案。
易错点
- 栈空时不补断点：后面所有长度都会从错误的起点算起。
- 忘记先压入 -1：第一个有效段会少算一个位置。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
s = "(()())"空串和单个字符都不可能有配对，dp[0]、dp[1] 先设为 0。
- s
- (()())
dp[i]：以 s[i-1] 结尾的最长有效括号长度；s = "(()())"
dp[0]=0查看 C++ 代码
延伸阅读
- “以 i 结尾”的 DP 适合处理带配对、带连续约束的字符串问题；子串不要求连续时会换成另一种状态。
- 括号匹配还可以用计数器加两次扫描求最长有效段，空间 O(1)，但边界更绕。