LeetCode 32：最长有效括号（Longest Valid Parentheses）题解

Longest Valid Parentheses 是 LeetCode Hot 100 里面一道非常经典的括号题。

如果说前面的“有效的括号”是在判断一个字符串整体是否合法，那么这道题就更进一步了： 它不是问你整个字符串是不是有效，而是问你：

这个字符串中，最长的有效括号子串有多长？

这也是很多人第一次做这题时容易绕进去的地方。因为“判断是否合法”和“寻找最长合法区间”虽然都和括号有关，但思维方式并不一样。 前者更像是一次整体匹配；而后者本质上是在字符串中不断寻找合法区间的边界。

你给出的这份 Java 代码，使用的是这道题最经典的一种解法：

栈 + 下标

这种写法非常巧妙，因为它不是把括号字符本身压栈，而是把 下标 压栈。这样我们就可以在匹配成功后，直接计算当前有效括号子串的长度。

本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给定一个只包含 '(' 和 ')' 的字符串 s，请你找出其中最长有效括号子串的长度。

这里的“有效括号子串”，指的是一段连续的、括号匹配合法的子串。

例如：

• "()" 是有效括号串，长度为 2

• "(())" 是有效括号串，长度为 4

• "(()" 中最长有效括号子串是 "()"，长度为 2

• ")()())" 中最长有效括号子串是 "()()"，长度为 4

题目要求返回的是最长那一段的长度，而不是返回具体的字符串。

示例

示例 1

输入：s = "(()"
输出：2

虽然整个字符串 "(()" 不是合法括号串，但其中的子串 "()" 是合法的，所以答案是 2。

示例 2

输入：s = ")()())"
输出：4

这个字符串中最长合法子串是：

"()()"

长度为 4。

示例 3

输入：s = ""
输出：0

空字符串中没有任何有效括号子串，所以答案是 0。

这道题和“有效的括号”有什么区别？

很多人在刷到这题时，第一反应会想到前面的 LeetCode 20：有效的括号。

但这两题虽然都和括号相关，考察重点其实完全不同。

有效的括号

问的是：

• 整个字符串是否合法

也就是说，只要有一个地方不匹配，整串就不行。

最长有效括号

问的是：

• 在整个字符串中，最长的合法连续子串有多长

哪怕整个字符串不合法，也不影响我们去寻找其中局部合法的部分。

所以这题的关键不在于“能不能匹配完全部括号”，而在于：

如何在扫描过程中，快速维护当前合法区间的长度。

最直接的想法为什么不好？

如果一开始直接暴力去想，很多人可能会想到：

• 枚举所有子串

• 判断每个子串是不是合法括号串

• 记录最长长度

这个思路当然可以做出来，但效率很低。

假设字符串长度是 n：

• 子串数量大约是 O(n^2)

• 每个子串再去判断是否合法，又要 O(n)

总时间复杂度就会变成：

O(n^3)

这显然太慢了。

所以我们需要一种更高效的方法，在一次遍历中尽量完成统计。

核心思路：为什么栈里要存下标？

你这段代码最关键的一点，就是：

栈里存的不是括号字符，而是下标。

为什么这么做？

因为题目最终要的不是“匹配成功了多少对括号”，而是：

最长有效括号子串的长度。

而一旦我们知道某个合法区间的左右边界下标，长度就能立刻算出来：

长度 = 右边界下标 - 左边界下标

所以这里最自然的做法，就是在栈里维护和边界有关的信息，而不是只维护字符本身。

整体思路

这道题的栈解法，核心可以概括成下面几步：

1. 栈里先压入一个 -1，作为初始边界

2. 遍历字符串：

   • 如果遇到 '('，就把它的下标压栈

   • 如果遇到 ')'，就先弹栈，表示尝试匹配一个左括号

3. 弹栈后：

   • 如果栈空了，说明当前右括号没有匹配对象，这个位置就成为新的边界，把当前下标压栈

   • 如果栈没空，说明当前形成了一个合法区间，长度就是：

     i – 栈顶下标

4. 在整个过程中维护最大值

这套写法非常精妙，尤其是“先压入 -1”和“栈空时压入当前下标”这两个细节，是整道题的关键。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    public int longestValidParentheses(String s) {
        int ans = 0;
        Deque<Integer> sta = new ArrayDeque<>();
​
        // 先放入一个哨兵，表示有效区间起点之前的位置
        sta.push(-1);
​
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                // 左括号下标入栈
                sta.push(i);
            } else {
                // 遇到右括号，先弹出一个位置，尝试匹配
                sta.pop();
​
                if (sta.isEmpty()) {
                    // 如果栈空了，说明当前右括号无法匹配
                    // 它将成为新的“起始边界”
                    sta.push(i);
                } else {
                    // 如果栈不空，说明当前形成了合法区间
                    ans = Math.max(ans, i - sta.peek());
                }
            }
        }
​
        return ans;
    }
}

代码拆解

这段代码虽然很短，但逻辑其实非常值得细抠。 下面一步一步来看。

1. 为什么一开始要压入 -1？

sta.push(-1);

这是整道题里最巧妙的一个细节。

这个 -1 可以理解成：

在字符串开始之前，先放一个“虚拟边界”。

为什么需要这个东西？

因为如果一开始就遇到一个完整的合法串，比如：

s = "()"

当遍历到右括号 ) 时，我们想计算当前合法区间长度：

i - 栈顶下标

如果没有这个 -1，那第一个左括号出栈之后，栈就空了，长度就没法正常算。

而有了 -1 之后：

• ( 的下标 0 入栈

• 遇到 ) 时，弹出 0

• 此时栈顶变成 -1

所以长度就是：

1 - (-1) = 2

正好正确。

所以这个 -1 本质上就是一个统一边界处理的“哨兵”。

2. 为什么左括号直接压入下标？

if (s.charAt(i) == '(') sta.push(i);

因为左括号目前还没有匹配对象，所以先把它的位置记下来。

注意，这里压的是下标 i，不是字符 '('。

这样做的目的是为了后面一旦匹配成功，就能直接根据位置来计算当前合法区间长度。

3. 为什么遇到右括号先弹栈？

sta.pop();

因为当前遇到了一个右括号，说明它想要去匹配最近的那个还没匹配的左括号。

而最近的未匹配左括号，正好就在栈顶。

所以这里先弹栈，表示“消耗掉一个待匹配位置”。

这个动作的含义可以这样理解：

• 如果栈顶原本是某个左括号下标，那么这次匹配成功

• 如果栈顶原本只是边界，那么弹完之后可能就空了，这说明当前右括号没有合法匹配对象

4. 为什么弹完之后如果栈空，就要把当前下标压进去？

if (sta.isEmpty()) {
    sta.push(i);
}

这一步是整道题另一个最关键的细节。

假设当前遇到一个无法匹配的右括号，比如：

s = ")()"

当第一个字符 ) 出现时，它前面根本没有左括号可以和它匹配。

这说明从这个位置开始，之前的区间已经彻底断开了。 换句话说，后面如果再出现新的合法区间，它的起点一定要在这个位置之后。

所以当前这个无法匹配的右括号下标，就应该被视为：

新的无效边界

因此把它压入栈中，后面再计算长度时，就可以把它当作起点前一个位置。

这一步可以简单理解成：

遇到无法匹配的右括号，就把它当作新的分隔点。

5. 为什么栈不空时，长度是 i - sta.peek()？

ans = Math.max(ans, i - sta.peek());

这一步是整个解法的核心。

当我们遇到右括号并弹栈后，如果栈还不空，说明当前右括号成功匹配了某个左括号，并且在当前位置结尾形成了一个合法区间。

那这个合法区间的左边界在哪里？

不是当前弹出的那个位置，而是：

当前栈顶之后的位置

所以区间长度就等于：

当前下标 i - 栈顶下标

比如：

s = "()"

流程是：

• 初始栈：[-1]

• 遇到 (：栈变成 [0, -1]

• 遇到 )：弹出 0，栈顶变回 -1

此时长度就是：

1 - (-1) = 2

再比如：

s = "()()"

当遍历到最后一个 ) 时，当前合法区间其实是整个字符串，长度应该是 4。 这时公式同样成立。

手动模拟一遍

我们用经典样例来走一遍：

s = ")()())"

初始状态

栈中先放入：

[-1]

最大值：

ans = 0

第 1 个字符：)，下标 0

遇到右括号，先弹栈：

• 栈从 [-1] 变成空

因为栈空了，说明这个右括号无法匹配，所以把当前下标压进去：

[0]

此时 ans = 0

第 2 个字符：(，下标 1

左括号入栈：

[1, 0]

第 3 个字符：)，下标 2

先弹栈：

• 弹出 1

• 栈变成 [0]

栈不空，说明当前形成合法区间。

长度为：

2 - 0 = 2

更新：

ans = 2

第 4 个字符：(，下标 3

左括号入栈：

[3, 0]

第 5 个字符：)，下标 4

先弹栈：

• 弹出 3

• 栈变成 [0]

栈不空，长度为：

4 - 0 = 4

更新：

ans = 4

第 6 个字符：)，下标 5

先弹栈：

• 弹出 0

• 栈空

说明这个右括号不能和前面再组成更长合法区间，所以把当前下标压入栈：

[5]

最终答案：

4

这正好对应最长合法子串 "()()"。

为什么这个算法是正确的？

因为栈始终维护的是：

• 尚未匹配的左括号下标

• 或者最近一个无法匹配的右括号下标（边界）

而当我们在某个位置 i 形成合法匹配后：

• 当前栈顶恰好就是这段合法区间左边界之前的位置

因此：

i - 栈顶下标

就正好是当前以 i 结尾的最长有效括号子串长度。

这个思路本质上是在用栈动态维护“最近的无效边界”。

复杂度分析

时间复杂度

整个字符串只遍历了一遍，每个下标最多入栈、出栈一次，所以时间复杂度是：

O(n)

空间复杂度

最坏情况下，比如字符串全是左括号：

"((((((("

那么所有下标都会入栈，因此空间复杂度是：

O(n)

这道题真正想考什么？

这道题表面上是在考括号，但本质上是在考两个能力。

第一，是否能把“括号匹配”转化为“区间长度”问题

很多人第一次做这题，会停留在“能不能匹配”的思维里。 但题目真正要的是最长长度，所以关键在于：

如何借助下标，快速得到区间范围。

这也是为什么栈里存的是下标，而不是字符。

第二，是否能理解“边界”的作用

这题最巧妙的地方不是匹配本身，而是：

• 初始的 -1

• 栈空时压入当前下标

这两个地方本质上都在维护边界。

一旦你理解了“无法匹配的位置，就是新的无效边界”这个思路，这道题就会一下子清晰很多。

这题还有别的解法吗？

有。

除了栈解法之外，这题还常见两种思路：

1. 动态规划

2. 左右计数扫描

不过从直观程度和代码可读性来说，栈解法通常是最容易理解的一种。 尤其是你现在这份代码，写法非常简洁，特别适合拿来当标准模板记忆。

总结

这道题的核心思想可以概括成一句话：

用栈维护未匹配的左括号位置和最近的无效边界，在每次匹配成功时计算当前有效区间长度。

完整流程就是：

1. 栈中先放入 -1 作为初始边界

2. 遇到左括号，把下标压栈

3. 遇到右括号，先弹栈

4. 如果弹完后栈空，说明当前右括号无法匹配，把当前下标作为新边界压栈

5. 如果栈不空，说明当前位置形成了合法区间，长度为 i - 栈顶下标

6. 在过程中不断更新最大值

这是一道非常经典、也非常值得反复理解的栈题。 因为它不仅考察栈的使用，更重要的是它让你体会到：

同样是括号问题，一旦题目目标从“判断合法”变成“求最长区间”，思维重点就会从字符匹配转向边界维护。

把这道题真正吃透之后，你对“栈 + 下标”这种套路会有很深的感觉。 以后再遇到需要求“最长合法区间”或者“最近边界”的题时，思路也会顺很多。