0032. Longest Valid Parentheses¶
题目信息¶
- 题号:
最长有效括号
- 难度:
Hard
- 主题:
字符串、栈、动态规划、双向扫描
- 原题:
- 重点:
从逐起点验证推导到维护失效边界,并复用以当前位置结束的最长有效段
题目重述¶
给定一个只包含 ( 和 ) 的字符串 s,返回其中最长有效括号连续子串的长度。
一个连续子串有效,当且仅当其中每个左括号都由后面的右括号闭合,并且从子串左端开始扫描时,任意前缀中的 右括号数量都不超过左括号数量。答案必须来自原字符串中的连续区间,不能跳过字符重新拼接。
字符串长度位于 [0, 3 * 10^4]。空字符串、全为左括号或全为右括号时,答案均为 0。
自建示例¶
多段连接:
s = "()(())",返回6;末尾的(())与前面的()连成完整区间;多余右括号:
s = ")(()())",返回6;下标0是任何有效区间都不能跨越的边界;多余左括号:
s = "(()(()",返回2;只有中间的()完整闭合;相邻有效段:
s = "()(()())",返回8;局部配对完成后还要连接左侧有效段;无法形成配对:
s = "(((",返回0。
C++ 实现¶
#include <algorithm>
#include <string>
#include <vector>
class Solution {
private:
int enumerateStarts(const std::string& s) {
int best = 0;
for (int start = 0; start < static_cast<int>(s.size()); ++start) {
int balance = 0;
for (int end = start; end < static_cast<int>(s.size()); ++end) {
balance += s[end] == '(' ? 1 : -1;
if (balance < 0) break;
if (balance == 0) {
best = std::max(best, end - start + 1);
}
}
}
return best;
}
int indexStack(const std::string& s) {
std::vector<int> boundaries{-1};
int best = 0;
for (int index = 0; index < static_cast<int>(s.size()); ++index) {
if (s[index] == '(') {
boundaries.push_back(index);
continue;
}
boundaries.pop_back();
if (boundaries.empty()) {
boundaries.push_back(index);
} else {
best = std::max(best, index - boundaries.back());
}
}
return best;
}
int dynamicProgramming(const std::string& s) {
std::vector<int> dp(s.size(), 0);
int best = 0;
for (int index = 1; index < static_cast<int>(s.size()); ++index) {
if (s[index] == '(') continue;
if (s[index - 1] == '(') {
dp[index] = 2;
if (index >= 2) {
dp[index] += dp[index - 2];
}
} else {
const int opening = index - dp[index - 1] - 1;
if (opening >= 0 && s[opening] == '(') {
dp[index] = dp[index - 1] + 2;
if (opening >= 1) {
dp[index] += dp[opening - 1];
}
}
}
best = std::max(best, dp[index]);
}
return best;
}
int bidirectionalCounters(const std::string& s) {
int best = 0;
int left = 0;
int right = 0;
for (char current : s) {
current == '(' ? ++left : ++right;
if (left == right) {
best = std::max(best, 2 * right);
} else if (right > left) {
left = 0;
right = 0;
}
}
left = 0;
right = 0;
for (int index = static_cast<int>(s.size()) - 1; index >= 0; --index) {
s[index] == '(' ? ++left : ++right;
if (left == right) {
best = std::max(best, 2 * left);
} else if (left > right) {
left = 0;
right = 0;
}
}
return best;
}
public:
int longestValidParentheses(std::string s) {
return dynamicProgramming(s);
}
};
题解¶
逐起点余额¶
固定起点 start 后,向右扫描并维护余额:左括号使余额加一,右括号使余额减一。余额为零时,左右括号数量
相等;此前余额从未为负,因此区间 [start,end] 有效。
余额首次变为负数时,当前前缀已经包含无法匹配的右括号。继续延长仍会保留这个非法前缀,所以同一起点不可能 再产生有效区间,可以立即停止。
enumerateStarts 按定义检查每个起点,正确性直接,但不同起点会反复读取相同后缀,最坏时间为
O(n²)。继续优化需要保存已经发现的非法边界或有效区间,而不是重新计算余额。
失效边界与下标栈¶
对一个以当前位置结束的有效后缀,真正决定其左边界的是最近一个不能跨越的位置:
尚未匹配的左括号;跨过它会使区间内左括号过多;
无法匹配的右括号;跨过它会使某个前缀右括号过多。
indexStack 用下标栈保存这些边界,初始放入 -1,表示字符串开头之前的虚拟边界。遇到左括号时压入
下标;遇到右括号时先弹出一个位置,尝试匹配最近的未匹配左括号。
若弹出后栈为空,当前右括号无法匹配,它成为新的失效边界。若栈仍非空,当前右括号成功完成一层配对,栈顶 就是当前有效后缀左侧最近的不可跨越位置,因此长度为:
index - boundaries.back()
栈顶之后不存在未匹配括号,跨过栈顶又必然破坏合法性,所以该长度恰好是以 index 结束的最长有效后缀。
每个下标最多入栈、出栈一次,时间降为 O(n)。
结束位置状态¶
下标栈保存全部未匹配边界。动态规划改为只保存每个结束位置的最优结果:
dp[i] = 以 s[i] 结尾的最长有效括号子串长度
左括号不能结束有效括号串,因此 s[i] == '(' 时 dp[i] = 0。当 s[i] == ')' 时,只需处理两种
末尾结构。
直接配对¶
若 s[i - 1] == '(',末尾两个字符直接形成 ()。它们左侧若紧邻一个以 i - 2 结束的有效段,两个
区间可以连接:
dp[i] = 2 + dp[i - 2]
下标越界时把前段长度视为零。例如 ()() 的最后一对闭合后,需要连接前面的 (),得到长度 4。
包裹前段¶
若 s[i - 1] == ')',前一位置可能已经结束一段长度为 dp[i - 1] 的有效区间。当前右括号若要继续向左
扩展,只能跳过这段完整区间,再检查其前一个字符:
opening = i - dp[i - 1] - 1
若 opening 越界或 s[opening] 不是左括号,当前右括号不能形成更长有效后缀。若该位置是左括号,它与
当前右括号包住前一段有效区间,先得到:
dp[i - 1] + 2
新形成的区间左侧还可能紧邻另一段有效括号,因此继续连接 dp[opening - 1]:
dp[i] = dp[i - 1] + 2 + dp[opening - 1]
这里没有跨过非法字符。dp[i - 1] 只覆盖紧贴 i - 1 的有效段,opening 是跳过该段后的相邻字符;
dp[opening - 1] 也只吸收紧贴 opening 左侧的有效段。整个转移始终由连续相邻区间组成。
状态演化¶
以 s = "()(())" 为例:
|
字符 |
|
状态来源 |
|---|---|---|---|
0 |
|
0 |
左括号不能结束有效串 |
1 |
|
2 |
下标 0 与 1 直接配对 |
2 |
|
0 |
左括号不能结束有效串 |
3 |
|
0 |
左括号不能结束有效串 |
4 |
|
2 |
下标 3 与 4 直接配对 |
5 |
|
6 |
跳过 |
最后一步若只计算 dp[4] + 2,只能得到 (()) 的长度 4。连接 dp[1] 后,才得到完整连续区间
()(()) 的长度 6。
双向计数¶
若只需要最长长度,不需要恢复区间边界,还可以只维护左右括号数量。
从左向右扫描时,right > left 表示出现无法匹配的右括号,当前段不能再延伸,计数清零;
left == right 表示当前重置点之后形成有效区间,用 2 * right 更新答案。
单次正向扫描无法处理末尾多余左括号,例如 (()。因此再从右向左对称扫描:此时 left > right 表示
无法匹配的左括号,需要清零;两者相等时用 2 * left 更新答案。两个方向共同覆盖多余右括号和多余左括号
形成的边界,额外空间降为 O(1)。
方法演进¶
enumerateStarts 为每个起点重新计算余额。indexStack 把重复扫描压缩为未匹配边界,使每个字符只处理一次。
dynamicProgramming 将问题改写为“以每个位置结束的最长有效段”,通过前一有效段、配对左括号和左侧相邻段
复用已经完成的区间。公开入口采用该方法,因为状态与转移都直接对应连续区间。
bidirectionalCounters 进一步放弃具体边界,只保存两类括号数量,以两个扫描方向换取常数空间。
复杂度分析¶
设字符串长度为 n。
方法 |
时间复杂度 |
工作空间 |
|---|---|---|
逐起点余额 |
|
|
下标栈 |
|
|
动态规划 |
|
|
双向计数 |
|
|
动态规划只计算每个 dp[i] 一次;双向计数各扫描字符串一次。返回值只保存长度,不计入额外空间。