最长有效括号：如何像扫描仪一样读取括号串
大家好！今天我们来挑战一道经典题目：最长有效括号。这个问题乍看有点抽象，但通过今天的讲解，我保证你能像阅读母语一样轻松看懂括号串。
🎯 问题本质：阅读"括号语言"
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效括号子串的长度。
例如：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"🤔 为什么这题不简单？
让我们先看看为什么这题不能用简单的计数解决：
例子：")()())"
如果只是计数：
- 左括号数=2
- 右括号数=4
这样算不出答案！关键难点在于：
- 括号必须匹配
- 必须是连续的子串
- 无效的括号会打断有效序列
💡 如何像人脑一样处理括号？
想象你在阅读一个括号串，你会怎么做？
看到这个串: "( ( ) ) ( )"
你的大脑可能是这样处理的：
1. 看到 (，等待匹配
2. 又看到 (，继续等待
3. 看到 )，匹配最近的 (
4. 看到 )，匹配剩下的 (
5. 发现形成了 "(())"
6. 继续处理后面的 "()"这个过程给了我们启发：我们需要一个"栈"来模拟大脑的记忆过程！
📝 栈解法：模拟大脑的处理流程
让我们来看看如何用栈来解决这个问题：
java
class Solution {
public int longestValidParentheses(String s) {
int maxLen = 0;
Stack<Integer> stack = new Stack<>();
// 放入-1作为哨兵，处理边界情况
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
// 左括号：把下标压入栈
stack.push(i);
} else {
// 右括号：弹出栈顶
stack.pop();
if (stack.isEmpty()) {
// 栈空了，说明右括号多了，记录新的起点
stack.push(i);
} else {
// 计算当前有效括号长度
maxLen = Math.max(maxLen, i - stack.peek());
}
}
}
return maxLen;
}
}🎨 图解栈的处理过程
让我们用一个例子详细看看栈是如何工作的：
s = ")()())"
1. 初始状态：
栈：[-1]
maxLen = 0
2. 遇到 )：
弹出-1
栈空了，放入0
栈：[0]
maxLen = 0
3. 遇到 (：
放入1
栈：[0,1]
maxLen = 0
4. 遇到 )：
弹出1
计算长度：2-0=2
栈：[0]
maxLen = 2
... 依此类推💫 另一种思路：动态规划
除了栈，我们还可以用动态规划来解决这个问题：
java
class Solution {
public int longestValidParentheses(String s) {
int maxLen = 0;
// dp[i]表示以i结尾的最长有效括号长度
int[] dp = new int[s.length()];
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
if (s.charAt(i-1) == '(') {
// 情况1：()
dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
} else if (i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '(') {
// 情况2：((...))
dp[i] = dp[i-1] + 2 +
(i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0);
}
maxLen = Math.max(maxLen, dp[i]);
}
}
return maxLen;
}
}🎯 动态规划解法图解
以 "(())" 为例：
初始：dp = [0,0,0,0]
遇到第一个)：i=1
s[0] = '('，s[1] = ')'
dp[1] = 2
dp = [0,2,0,0]
遇到第二个)：i=3
s[2] = '('，s[3] = ')'
之前有dp[1]=2个匹配
dp[3] = dp[1] + 2 = 4
dp = [0,2,0,4]💡 解题技巧
栈解法技巧：
- 用-1作为哨兵，简化边界处理
- 栈里存放下标而不是括号字符
动态规划技巧：
- 只需要关注右括号位置
- 考虑两种基本模式：() 和 ((...))
🎓 面试指南
遇到这题时，建议这样回答：
先说明问题的关键点：
- 括号必须匹配
- 子串必须连续
- 需要找最长长度
提供两种解法：
- 栈解法：直观模拟人脑处理过程
- 动态规划：数学归纳思维
分析两种解法的优缺点：
- 栈：思路直观，空间复杂度O(n)
- DP：思路巧妙，空间复杂度O(n) 时间复杂度都是O(n)
🔍 相似题目
- 有效的括号
- 括号生成
- 删除无效的括号
🤔 思考题
如果要求不仅返回长度，还要返回具体的最长有效括号子串，该如何修改代码？
作者：忍者算法
公众号：忍者算法
括号匹配问题是算法中的经典问题，它不仅考察了我们对栈和动态规划的理解，更锻炼了我们处理序列性问题的思维能力。希望这篇文章能帮助你掌握这类问题的解题思路！
#算法面试 #LeetCode #动态规划 #栈