最长有效括号 图解题解

这道题到底在问什么

输入

s = "(()"

输出

2

解释

最长有效括号子串是 "()"

输入

s = ")()())"

输出

4

解释

最长有效括号子串是 "()()"

输入

s = ""

输出

0

先想最直接的笨办法

枚举所有子串是 O(n 平方) 个，每个再扫一遍判断合法是 O(n)，合起来 O(n 的三次方)。字符串长度到 3 万时直接超时。（动画第 3 步）

最优解：一步一步想明白

1. 3枚举所有子串是 O(n 平方) 个，每个再扫一遍判断合法是 O(n)，合起来 O(n 的三次方)。字符串长度到 3 万时直接超时。
2. 4遇到 "(" 就压入它的下标；遇到 ")" 先弹一个。弹完后栈空，说明这个 ")" 是新的非法边界；栈不空，当前合法长度就是 i 减去栈顶下标。
3. 5一开始先压一个哨兵 −1，代表字符串开始前的边界。这样从下标 0 开始的合法串，也能用 i 减栈顶算出长度。
4. 6执行：stack = [-1]; ans = 0我们用例子 ")()())" 来演。先把哨兵 −1 压进栈，它代表「开头之前」这条看不见的左墙。
5. 7执行：stack.pop()开头就是右括号，肯定配不上谁。代码统一处理：遇到 ")" 一律先 pop。这一弹，连哨兵 −1 都被弹掉了，栈空了。
6. 8执行：if not stack: stack.append(0)弹完栈空，说明这个 ")" 没配上。把它自己的下标 0 压回去，当新的左墙——后面的合法段都不许跨过它。
7. 9执行：stack.append(1)左括号还没被匹配，把它的下标 1 压栈。栈底那个 0 仍然是不能跨过的边界。
8. 10执行：stack.pop()这个右括号配上了下标 1 的左括号，弹掉它。弹完后栈顶露出 0，它就是当前合法段左边的边界。
9. 11执行：ans = max(ans, 2 − 0) = 2栈不空，关键的一步来了：长度不是「刚才那一对」，而是 i 减栈顶。以下标 2 结尾的合法段是 1..2，长度 2。
10. 12执行：stack.append(3)又一个左括号，压入下标 3。它可能跟后面的右括号组成新的一对，也可能跟前面的合法段连起来。
11. 13执行：stack.pop()下标 3 和 4 配成一对，弹掉 3。重点：别只盯这一对，弹完后看栈顶是谁，决定它能不能跟前面连上。
12. 14执行：ans = max(ans, 4 − 0) = 4栈顶还是 0，说明从下标 1 到 4 中间没被任何非法右括号切断。所以这段是 "()()"，长度 4 — 这正是「存下标」的威力。
13. 15执行：stack.pop()最后一个右括号没有对应的左括号。弹掉栈顶 0 后栈空，说明它要成为新的非法边界。
14. 16执行：stack.append(5)非法右括号只负责切断后面的连续段，它自己不更新答案。当前最好成绩仍是前面算出的 4。
15. 17执行：return ans整串扫完，ans 里存的就是最长有效括号子串长度。对 ")()())" 答案是 4。
16. 18回放：i=4 弹掉 3 → 栈顶=0 → 长度 4−0=4把整题压成一句话：右括号先弹，弹完看栈顶。栈空就把自己当新墙；栈不空，i 减栈顶就是以 i 结尾的最长合法段。这一步是全题唯一的命门，记住它就够了。
17. 21一旦答案跟距离、长度、区间有关，栈里往往该存下标而不是值——这是括号长度题最值钱的一句迁移点。
18. 23错误写法：ans = i − 刚弹掉的 3 = 4 − 3 = 1（漏算前面）在 i=4 这一步，如果用「i 减刚弹掉的下标 3」，只会得到这一对的长度，把前面连着的 "()" 漏掉，答案被压成更小的值。必须用弹完后的栈顶 0，才能把相邻合法段接上得到 4。
19. 28先吃透 20 题括号匹配（存字符），再到 32 题最长有效（存下标），就能迁移到 84 柱状图最大矩形、739 每日温度这类「栈存下标算距离」的题。想系统练可以点右侧的栈专题，或问问 AI 助教「下标栈还能解哪些题」。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def longestValidParentheses(self, s):
        stack = [-1]            # 哨兵：开头前的边界
        ans = 0
        for i, ch in enumerate(s):
            if ch == '(':
                stack.append(i)    # 左括号压下标
            else:                  # 右括号
                stack.pop()        # 先弹一个
                if not stack:      # 弹空了
                    stack.append(i)        # 自己当新边界
                else:
                    ans = max(ans, i - stack[-1])  # i 减栈顶
        return ans

class Solution {
public:
    int longestValidParentheses(string s) {
        vector<int> st{-1};        // 哨兵边界
        int ans = 0;
        for (int i = 0; i < (int)s.size(); i++) {
            if (s[i] == '(') st.push_back(i);
            else {                 // 右括号
                st.pop_back();
                if (st.empty()) st.push_back(i);
                else ans = max(ans, i - st.back());
            }
        }
        return ans;
    }
};

class Solution {
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1);            // 哨兵边界
        int ans = 0;
        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 ans = Math.max(ans, i - stack.peek());
            }
        }
        return ans;
    }
}

stack = [-1]              # 哨兵：第一段/第一个距离的起点边界
ans = 0
for i, ch in enumerate(s):
    if 是入栈条件(ch):      # 如 '(' / 比栈顶高 / 未匹配
        stack.append(i)
    else:
        stack.pop()          # 先弹掉被结算的那个
        if not stack:        # 弹空 → 当前 i 是新边界
            stack.append(i)
        else:
            ans = max(ans, i - stack[-1])  # 用「弹完后的栈顶」算跨度
return ans

vector<int> st{-1};            // 哨兵边界
int ans = 0;
for (int i = 0; i < (int)s.size(); i++) {
    if (/* 入栈条件 */) st.push_back(i);
    else {
        st.pop_back();
        if (st.empty()) st.push_back(i);     // 新边界
        else ans = max(ans, i - st.back());  // 弹完后栈顶
    }
}
return ans;

Deque<Integer> st = new ArrayDeque<>();
st.push(-1);                   // 哨兵边界
int ans = 0;
for (int i = 0; i < s.length(); i++) {
    if (/* 入栈条件 */) st.push(i);
    else {
        st.pop();
        if (st.isEmpty()) st.push(i);                 // 新边界
        else ans = Math.max(ans, i - st.peek());      // 弹完后栈顶
    }
}
return ans;

复杂度

面试官可能追问