32. 最长有效括号#

大家好！今天我们来挑战一道经典题目：最长有效括号。这个问题乍看有点抽象，但通过今天的讲解，我保证你能像阅读母语一样轻松看懂括号串。

🎯 问题本质：阅读”括号语言”#

给你一个只包含 ’(’ 和 ’)’ 的字符串，找出最长有效括号子串的长度。

例如：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

plaintext

问题描述#

题目目标#

给定一个只包含 ( 和 ) 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1#

输入： s = ")()())" 输出： 4 说明： 最长有效括号子串为 ”()()“，长度为 4

🤔 为什么这题不简单？#

让我们先看看为什么这题不能用简单的计数解决：

例子：")()())"
如果只是计数：
- 左括号数=2
- 右括号数=4
这样算不出答案！

plaintext

关键难点在于：

括号必须匹配
必须是连续的子串
无效的括号会打断有效序列

💡 如何像人脑一样处理括号？#

想象你在阅读一个括号串，你会怎么做？

看到这个串: "( ( ) ) ( )"

你的大脑可能是这样处理的：
1. 看到 (，等待匹配
2. 又看到 (，继续等待
3. 看到 )，匹配最近的 (
4. 看到 )，匹配剩下的 (
5. 发现形成了 "(())"
6. 继续处理后面的 "()"

plaintext

这个过程给了我们启发：我们需要一个”栈”来模拟大脑的记忆过程！

📝 栈解法：模拟大脑的处理流程#

让我们来看看如何用栈来解决这个问题：

class Solution {
    public int longestValidParentheses(String s) {
        // maxLen 记录扫描过程中出现过的最长有效括号长度
        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 {
                    // 栈顶现在是“当前有效段之前的最近未匹配位置”
                    // 所以当前有效长度 = i - stack.peek()
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        // 返回最长有效括号长度
        return maxLen;
    }
}

java

🎨 图解栈的处理过程#

让我们用一个例子详细看看栈是如何工作的：

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

... 依此类推

plaintext

💫 另一种思路：动态规划#

除了栈，我们还可以用动态规划来解决这个问题：

class Solution {
    public int longestValidParentheses(String s) {
        // maxLen 保存全局最长有效括号长度
        int maxLen = 0;
        // dp[i]表示以i结尾的最长有效括号长度
        int[] dp = new int[s.length()];

        // 从下标 1 开始，因为有效括号至少需要两个字符
        for (int i = 1; i < s.length(); i++) {
            // 只有当前位置是右括号，才可能形成有效括号结尾
            if (s.charAt(i) == ')') {
                // 情况 1：...()，即前一个字符正好是 '('
                if (s.charAt(i-1) == '(') {
                    // 情况1：()
                    // 当前长度 = 2 + i-2 位置的有效长度（如果存在）
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                // 情况 2：...))，尝试与更前面的 '(' 配对，形成 ...((...))
                } else if (i - dp[i-1] > 0 && s.charAt(i - dp[i-1] - 1) == '(') {
                    // 情况2：((...))
                    // 基础长度：前一个有效段 dp[i-1] + 新配对的一对括号 2
                    // 再加上更前面可能连接的有效段 dp[i - dp[i-1] - 2]
                    dp[i] = dp[i-1] + 2 + 
                           (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0);
                }
                // 每次更新 dp[i] 后，都尝试刷新全局最优
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        // 返回最终答案
        return maxLen;
    }
}

java

🎯 动态规划解法图解#

以 ”(())” 为例：

初始：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]

plaintext

💡 解题技巧#

栈解法技巧：
- 用-1作为哨兵，简化边界处理
- 栈里存放下标而不是括号字符
动态规划技巧：
- 只需要关注右括号位置
- 考虑两种基本模式：() 和 ((…))

🎓 面试指南#

遇到这题时，建议这样回答：

先说明问题的关键点：
- 括号必须匹配
- 子串必须连续
- 需要找最长长度
提供两种解法：
- 栈解法：直观模拟人脑处理过程
- 动态规划：数学归纳思维
分析两种解法的优缺点：
- 栈：思路直观，空间复杂度O(n)
- DP：思路巧妙，空间复杂度O(n) 时间复杂度都是O(n)

🔍 相似题目#

有效的括号
括号生成
删除无效的括号

🤔 思考题#

如果要求不仅返回长度，还要返回具体的最长有效括号子串，该如何修改代码？

括号匹配问题是算法中的经典问题，它不仅考察了我们对栈和动态规划的理解，更锻炼了我们处理序列性问题的思维能力。希望这篇文章能帮助你掌握这类问题的解题思路！