最长有效括号 图解题解

最长有效括号这道题在问什么

在一个只含左右括号的串里，找最长的一段连续子串，使它是完全合法、能全部配对的括号串。注意两点：一是要求连续子串而不是子序列，中间一个落单的右括号就会把有效段拦腰切断；二是答案只要长度这个数字，不用输出子串本身。

会判合法为什么还不够，栈里为什么存下标

用栈判断括号串是否合法是基本功：左括号进栈，右括号消掉一个栈顶。但本题要的是长度，只知道「配上了」远远不够，还得知道这一段合法串从哪里开始。这逼出关键的一步改造：栈里不存括号字符，改存下标。位置信息进了栈，长度才有得算——某段合法串的长度，就是它右端点减去左端点前面那个位置。

于是问题聚焦成一件事：扫到位置 i 收获一个配对时，怎么快速知道「以 i 结尾的有效段」左端在哪。答案藏在栈的形态里。

栈底为什么始终是当前段左边界的前一位

算法维持这样一条不变量：栈底永远存着「当前有效段左边界的前一个下标」，栈里其余元素是还没配对的左括号下标。开局先压 -1，代表最初的有效段可以从下标 0 起步。扫描规则：遇左括号压 i 占位；遇右括号先弹一个——若弹后栈非空，说明配对成功，i - stack[-1] 就是以 i 结尾的最长有效长度，拿去刷新最大值；若弹空了，说明这个右括号没有搭档，它是新的断点，把 i 压入接任边界。

断点接任边界这步是灵魂：后面的有效段无论多长都跨不过这个孤儿右括号，所以从它之后重新起算，正好由「i 减栈底」自动兑现。

相邻有效段的拼接为什么自动发生

很多人担心 ()(()) 这种「两段挨着」的情形要不要特判，其实不用。以串 ()(()) 为例：扫到最后一个右括号时，中间所有配对的下标都已被成双弹掉，栈里只剩最初的 -1，i - (-1) = 6 一次量出整段长度。原因在于：只要两段之间没有断点，中间的下标就不会滞留在栈里，i 减栈顶天然跨过所有已配对的部分，合并不需要任何额外逻辑。

复杂度与常见翻车点

时间 O(n)，每个字符至多进出栈一次；空间 O(n)，最坏全是左括号全部压栈。三个高频错误：忘了先压 -1，第一段合法串的长度就量不出来；右括号弹空后忘记把 i 压回去，断点丢失、后面全部算错；以及栈里存字符而不是下标，长度无从谈起。若追求 O(1) 空间，还有左右各扫一遍的双计数器解法，以及 dp[i] 表示以 i 结尾最长有效长度的动态规划解法，思路殊途同归。

Python

def longestValidParentheses(s: str) -> int:
    stack = [-1]          # 先压左边界
    best = 0
    for i, c in enumerate(s):
        if c == "(":
            stack.append(i)   # 压下标占位
        else:
            stack.pop()
            if stack:
                best = max(best, i - stack[-1])
            else:
                stack.append(i)  # 新边界
    return best

C++

int longestValidParentheses(string s){
    stack<int> st; st.push(-1);
    int best = 0;
    for(int i = 0; i < (int)s.size(); i++){
        if(s[i] == '(') st.push(i);
        else {
            st.pop();
            if(!st.empty()) best = max(best, i - st.top());
            else st.push(i);
        }
    }
    return best;
}

Java

public int longestValidParentheses(String s){
    Deque<Integer> st = new ArrayDeque<>();
    st.push(-1);
    int best = 0;
    for(int i = 0; i < s.length(); i++){
        if(s.charAt(i) == '(') st.push(i);
        else {
            st.pop();
            if(!st.isEmpty()) best = Math.max(best, i - st.peek());
            else st.push(i);
        }
    }
    return best;
}