求最长有效括号子串。

核心回答

可以用存下标的栈在线性时间内求出最长有效括号子串。先确认输入只包含 (、)，返回的是最长连续子串的长度；空串或没有有效子串时返回 0。

栈底先放 -1，作为字符串起点之前的边界。遇到左括号，把下标入栈；遇到右括号，先弹出栈顶：如果栈空，说明这个右括号无法匹配，就把当前位置作为新的边界；如果栈还在，当前位置 - 栈顶下标 就是以当前右括号结尾的最长有效长度。

关键不是累计匹配了多少对，而是记住当前有效片段不能跨过的最近边界。这样既能处理嵌套，也能把 ()() 这样的相邻片段合起来。时间复杂度 O(n)，最坏空间复杂度 O(n)。

Python 实现

def longest_valid_parentheses(s: str) -> int:
    stack = [-1]  # 栈底记录边界，其余下标对应尚未匹配的左括号
    best = 0

    for i, char in enumerate(s):
        if char == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)  # 无法匹配的右括号，后续有效子串从它之后开始
            else:
                best = max(best, i - stack[-1])

    return best

这里按题目限定只接收两种括号，所以 else 代表右括号。若输入还可能包含其他字符，需要先约定它们是非法输入还是分隔符，再调整处理方式。

栈顶为什么能用来计算长度？

一次迭代结束后，栈底是最近一个无法匹配的右括号位置，或初始的 -1；其余元素是尚未匹配的左括号下标。

当右括号成功配对并弹出一个左括号后，剩下的栈顶有两种情况：

• 是尚未匹配的左括号：以当前右括号结尾的有效片段不能包含它，只能从它后面开始。
• 是栈底边界：当前这段已经没有未配对的左括号，可以一直延伸到边界后面。

因此，起点都是 stack[-1] + 1，长度是 i - stack[-1]。如果弹出后栈空，这次弹掉的是旧边界，说明当前右括号无法配对；先更新边界，再继续扫描，不能在空栈上取下标。

初始值 -1 也让从字符串首位开始的答案可以统一计算。例如 "()" 在下标 1 匹配后，栈为 [-1]，长度就是 1 - (-1) = 2。

用 )()()) 走一遍

下标从 0 开始：

1. 下标 0 是 )，弹出 -1 后栈空，把 0 记为边界，栈为 [0]。
2. 下标 1 是 (，入栈，得到 [0, 1]。
3. 下标 2 是 )，弹出 1，得到 [0]，有效长度为 2 - 0 = 2。
4. 下标 3 是 (，入栈，得到 [0, 3]。
5. 下标 4 是 )，弹出 3，得到 [0]，有效长度为 4 - 0 = 4，对应 "()()"。
6. 下标 5 是 )，弹出 0 后栈空，更新边界为 5；已找到的最大值 4 保留。

这也说明，只计算当前配对的左、右括号距离是不够的：第二对 () 自己长 2，但它能和前一对连接成长度 4 的有效子串。

复杂度与边界

每个下标最多入栈、出栈各一次，所以总时间为 O(n)。最坏情况下全是左括号，栈存下所有下标，额外空间为 O(n)。Python 列表在尾部执行 append、pop，无需从头部移动元素。

可以先用这些例子检查实现：

• ""、"((("、")))"、")("：均为 0。
• "(()"：2，未闭合的左括号不能计入答案。
• "()()"：4，相邻有效段应当合并。
• "(())"：4，嵌套也能处理。
• ")()())"：4，不能跨过多余右括号。
• "()(()"：2；虽然可以挑出两对括号，但它们不构成长度 4 的连续有效子串。

常见追问

如果要求返回子串本身呢？

在更新最大值时，同时记录起点 stack[-1] + 1，扫描结束后取对应长度的切片即可。若最长答案有多个，还要约定返回第一个、任意一个还是全部；只在长度严格变大时更新起点，可以保留第一个。

可以用动态规划吗？

可以。定义 dp[i] 为以第 i 个字符结尾的最长有效长度，只有右括号可能产生非零值。转移时要处理直接形成 ()，以及跨过已有有效段后再向前匹配两种情况，还要把前面相邻的有效段接起来。它同样可做到 O(n) 时间、O(n) 空间；这道题用边界栈更容易把下标关系讲清楚。

怎样把额外空间降到 O(1)？

可以左右各扫描一次，统计左、右括号数量。正向扫描时数量相等就更新长度，右括号更多就重置；反向扫描时对称处理，左括号更多就重置。只扫一个方向会漏掉例如 "(()" 这类末尾存在未配对左括号的情况，因此两次扫描各自负责一种不平衡。

参考资料