最长有效括号
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。
示例 1
"()"。示例 2
"()()"。示例 3
模拟答题者思考
1. 我先想暴力：枚举所有子串，对每个子串用栈或计数判断括号是否有效，取最长——能过但 O(n³) 或 O(n²)，3×10⁴ 的数据会超时。
2. 重复在哪里？每遇到一个 ')'，它只能与「离它最近、尚未匹配」的 '(' 配对——又是后进先出；但本题要的是最长连续有效子串，不是判断整串是否有效。
3. 关键转化：栈里不存字符，存下标。压入哨兵 -1 表示「有效段起点的前一位」；每次 ')' 弹出匹配的 '(' 后，当前有效段长度 = 当前下标 - 栈顶下标。
4. 若弹出后栈空，说明这个 ')' 无法配对（如开头就是 ')'），把它压回栈作为新的「分割点」，后面的有效段从这里重新计算。
5. 例 ")()())"：遇到开头 ')' 后栈只剩 [2] 作基准，随后 () 得长度 2，再 () 得长度 4；全程 O(n) 一遍扫描。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
stk | list / stack | 定义：存放「尚未被匹配的左括号下标」以及作为基准的哨兵下标 维护：栈顶对应当前有效子串的「左边界前一位」；初始压入 -1 作为全局基准更新：遇 '(' 压入下标 i；遇 ')' 先 pop，栈空则压入 i 重置基准，否则用 i - stk[-1] 更新答案 |
ans | int | 定义：截至目前发现的最长有效括号子串长度 维护：单调不减，记录全局最优 更新：每次成功匹配右括号后，计算 i - stk[-1] 并与 ans 取 max |
i | int | 定义：当前扫描到的字符下标 维护：从左到右依次处理每个括号 更新：每轮循环 i += 1，根据 s[i] 是左/右括号分支更新栈与答案 |
落码步骤
1. 初始化 stk = [-1]（哨兵）、ans = 0
2. 从左到右遍历下标 i 与字符 s[i]
3. 若 s[i] == '('，将 i 压入栈，等待后续右括号匹配
4. 若 s[i] == ')'：先 stk.pop() 弹出待匹配的左括号（或哨兵）
5. 弹出后若栈空，说明当前 ')' 无法配对，将 i 压栈作为新基准；否则 ans = max(ans, i - stk[-1])
6. 遍历结束返回 ans
代码实现
class Solution:
def longestValidParentheses(self, s: str) -> int:
stk = [-1] # 哨兵：有效段左边界的前一位
ans = 0
for i, ch in enumerate(s):
if ch == '(':
stk.append(i)
else:
stk.pop() # 匹配掉一个 '(' 或哨兵
if not stk:
stk.append(i) # 多余的 ')'，作为新分割点
else:
ans = max(ans, i - stk[-1])
return ansclass Solution {
public:
int longestValidParentheses(string s) {
vector<int> stk = {-1}; // 哨兵：有效段左边界的前一位
int ans = 0;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == '(') {
stk.push_back(i);
} else {
stk.pop_back(); // 匹配掉一个 '(' 或哨兵
if (stk.empty()) {
stk.push_back(i); // 多余的 ')'，作为新分割点
} else {
ans = max(ans, i - stk.back());
}
}
}
return ans;
}
};
// 时间 O(n)，空间 O(n)复杂度分析
O(n)
O(n)
常见坑
栈里存字符而不是下标：无法计算子串长度，也无法在多余 ')' 处设置分割点。
忘记初始哨兵 -1：第一个完整段 "()" 在 i=1 时栈顶为空，长度会变成 1-0=1 而非 2。
弹出后栈空时忘记压入当前 i：后续有效段会把前面无法配对的 ')' 也算进去，导致长度偏大。
必测边界 Case
s = "" → 0
s = "(()" → 2（末尾多余 '(' 留在栈中，不影响已算出的 "()"）
s = ")()())" → 4（开头 ')' 触发重置基准，最长段为 "()()"）