LeetCode 32：最长有效括号 —— 栈 + 标记法 题解
🔗 题目链接
👉 https://leetcode.cn/problems/longest-valid-parentheses/
📖 题目概要
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（连续、合法）括号子串的长度。
- 有效括号：必须成对、顺序正确、连续
- 示例："(()" → 输出 2；")()())" → 输出 4
✅ 本题解法：栈 + 标记法（你的 AC 代码思路）
核心思想
💡 详细解题思路
1. 算法步骤
- 第一步：遍历字符串，遇到 ( 就把下标压入栈
- 第二步：遇到 ) 时，如果栈不为空，说明匹配成功
- 弹出栈顶下标 j
- 把 mask[j] 和 mask[i] 都标记为 1
- 第三步：遍历 mask 数组，统计最长连续 1的长度，就是最长有效括号长度
2. 为什么这个方法正确？
- 只有真正成对匹配的括号才会被标记 1
- 有效括号一定是连续一段，所以直接求最长连续 1 即可
- 时间、空间都很优秀，逻辑直观易懂
✅ AC 代码（你的原版代码，可直接提交）
class Solution {
public int longestValidParentheses(String s) {
int len = s.length();
if(len <= 1) return 0;
char[] ss = s.toCharArray();
int[] mask = new int[len];
Deque<Integer> stack = new LinkedList<Integer>();
// 第一步：栈匹配括号，标记合法位置
for(int i=0;i<len;i++) {
if(ss[i] == '(') {
stack.push(i);
} else {
if(!stack.isEmpty()) {
int j = stack.pop();
mask[i] = 1;
mask[j] = 1;
}
}
}
// 第二步：找最长连续 1 的长度
int res = 0;
int cur = 0;
for(int i=0;i<len;i++) {
if(mask[i] == 1) {
cur++;
res = Math.max(res,cur);
} else {
cur = 0;
}
}
return res;
}
}
⏱️ 复杂度分析
| 时间复杂度 | O(n) | 仅两次线性遍历 |
| 空间复杂度 | O(n) | 栈 + mask 数组开销 |
📌 核心总结
📝 面试高频问答
1. 为什么要存下标，不存字符？
因为我们需要标记位置，最后统计连续合法段长度。
2. 为什么最后要遍历 mask 数组？
因为有效括号一定是连续的，最长连续 1 就是最长有效长度。
3. 这个方法和纯 DP 比有什么优势？
- 逻辑更简单
- 不用推导 DP 方程
- 代码短、不容易写错
