#32

困难

中频

栈

最长有效括号

这是一道围绕字符串展开的高频练习。建议先掌握「栈」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

字符串

原题练习

题目分析

给你一个只由 ( 和 ) 组成的字符串。

要求找出其中最长的一段连续有效括号子串，并返回它的长度。

比如 )()()) 里，最长有效括号子串是 ()()，长度是 4。

一句话概括：

在括号字符串里，找出最长的一段连续合法括号区间。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：栈里存下标，先放一个哨兵边界；遇到匹配右括号时，用当前下标减去栈顶得到合法长度。

结构化讲解

面试时怎么讲

开场思路

这题我会用“存下标的栈”，因为目标不只是判断合法，还要算最长长度。

核心过程

先在栈里压入 -1 作为初始边界。
遍历字符串，左括号压下标，右括号就弹栈尝试匹配。
如果弹完栈空，说明当前右括号失配，要把它当新边界压回去。
如果栈不空，就用当前下标减去栈顶下标，更新最长有效长度。

复杂度总结

时间复杂度 O(n)，空间复杂度 O(n)。

面试补一句：这题真正有价值的技巧是“栈里存下标 + 哨兵边界”。

核心思路

最长有效括号的难点不只是匹配，而是如何快速得到“当前合法区间长度”。把下标放进栈里，再加一个哨兵边界，就能在匹配成功时直接计算长度。

步骤讲解

先压入一个哨兵下标

在正式遍历前先把 -1 压栈，作为最左边界。

为什么这样做：这样第一个合法区间也能统一用下标差计算长度。

对应代码提示：stack.push(-1);

左括号压下标，右括号尝试弹栈匹配

遇到 ( 就压当前下标；遇到 ) 就先弹出一个下标，表示尝试匹配一对括号。

为什么这样做：栈里保存的是最近未匹配左括号的位置。

对应代码提示：if (s.charAt(i) == '(') stack.push(i); else stack.pop();

栈空时重置边界，不空时更新答案

若弹栈后栈空，说明当前右括号无法匹配，需把它作为新边界压回去；否则用 i - stack.peek() 更新最大长度。

为什么这样做：栈顶始终表示当前合法区间左边最近的无效边界。

对应代码提示：if (stack.isEmpty()) stack.push(i); else ans = Math.max(ans, i - stack.peek());

易错点

栈里只存括号不存下标

这样知道能否匹配，却没法快速计算合法区间长度。

正确理解：这题栈里必须存下标，而不是字符本身。

没放哨兵边界

第一个合法区间和断开的新区间边界都不好统一处理。

正确理解：遍历前先压 -1，并在失配时压入当前下标。

右括号失配后没重置边界

后面的长度计算会跨过无效位置，得到错误答案。

正确理解：弹栈后若栈空，要把当前下标重新压栈作为新起点。

复杂度与适用判断

时间复杂度：O(n)

空间复杂度：O(n)

比其他方案更好在哪里：比暴力枚举所有子串快很多，也比 DP 更容易现场推导。

适用判断：括号题里既要匹配关系，又要区间长度时，优先考虑“下标栈”。

额外提醒

栈顶不是当前匹配位置，而是当前合法区间左边最近的无效边界。

其他语言 / 其他解法

动态规划

算法思路待补充

时间复杂度：O(?)

空间复杂度：O(?)

一句话思路：算法思路待补充

// Java 实现 - 动态规划
class Solution {
    public int longestValidParentheses(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }
}

双指针

算法思路待补充

时间复杂度：O(?)

空间复杂度：O(?)

一句话思路：算法思路待补充

// Java 实现 - 双指针
class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, maxlength = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * right);
            } else if (right > left) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                maxlength = Math.max(maxlength, 2 * left);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return maxlength;
    }
}

动画演示

如果你还没完全看懂，可以展开动画演示。

栈动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

括号字符串:

准备就绪 - 输入括号字符串，然后点击开始

动态规划动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

括号字符串:

准备就绪 - 输入括号字符串，然后点击开始

双指针动画演示

想看这段解法是怎么一步步运行的，可以展开动画继续观察。

括号字符串:

准备就绪 - 输入括号字符串，然后点击开始

动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。