京公网安备11010502063487号给定一个只包含 ( 和 ) 的字符串，找出最长的有效（格式正确且连续）括号子串的长度。做法有好几种：栈、动态规划、正反两次计数。这道题容易写错的地方是：有效的括号段之间可能被没有配上的括号隔开，也可能几段相邻拼成更长的一段，所以不能只统计配对了多少对。本文用真实数据展示"配对个数乘 2"的错误，验证四种做法答案完全一致并比较耗时，给出五种语言的栈解法实现，并把栈的变化做成分步演示。
完整题目见官方页面（链接在文末）。基准解是暴力扫描：枚举每个起点，向右扫描并统计"左括号数减右括号数"，遇到负数就停止，回到 0 就说明是一段有效括号，取最长。它与栈解法完全不同。一共 14 组用例，覆盖：官方示例、空串、单个括号、只有右括号在前、被打断的两段、相邻的两段拼成更长的一段：
输入 ["(()"]
输出 2
输入 [")()())"]
输出 4
输入 [""]
输出 0
输入 ["("]
输出 0
输入 [")"]
输出 0
输入 ["()"]
输出 2一个直觉的做法是：用栈数一共配成了多少对，答案就是对数乘 2。但配对成功的括号未必连在一起。下面是这种写法与 solve 的真实结果：
# 「配对个数 × 2」的写法
'()(()': 配对个数×2 -> 4 solve -> 2
'()(()()': 配对个数×2 -> 6 solve -> 4
')()())': 配对个数×2 -> 4 solve -> 4
'(()(((()': 配对个数×2 -> 4 solve -> 2
'()()': 配对个数×2 -> 4 solve -> 4()(() 里成功配了 2 对，但它们被一个没配上的 ( 隔开了，最长的连续有效段只有 ()，长度 2，而不是 4；(()(((() 也是同样的情形。()(()() 里最长的有效段是后面的 (()()) 的长度 4，而配对总数是 3，不是最长段。只有整段都是连续配好的（如 ()()）时，两种算法才碰巧一致。
栈里放下标，而不是括号字符。栈底放一个 -1，表示"最后一个没能匹配的位置"在字符串之前。遇到 ( 就把它的下标入栈；遇到 ) 就弹出栈顶：弹完之后如果栈空了，说明这个 ) 没有 ( 可配，把它的下标压进去作为新的"最后一个没能匹配的位置"；否则栈顶就是这一段有效括号之前的分界，当前下标减去栈顶就是这一段的长度。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(s): st = [-1] # 栈里放下标；栈底始终是"最后一个没能匹配的位置" best = 0 for i, ch in enumerate(s): if ch == "(": st.append(i) else: st.pop() # 尝试匹配：弹出一个左括号（或栈底） if not st: # 栈空了：这个右括号没有左括号可配，成为新的"栈底" st.append(i) else: best = max(best, i - st[-1]) # 现在栈顶之后的一整段都是合法的 return best
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON
["(()"] → 2
[")()())"] → 4
[""] → 0
["("] → 0
[")"] → 0
["()"] → 2Java · 解法代码class Solution { 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()) st.push(i); // 栈空了：这个右括号成为新的"栈底" else best = Math.max(best, i - st.peek()); // 栈顶之后的一整段都是合法的 } } return best; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl
["(()"] → 2
[")()())"] → 4
[""] → 0
["("] → 0
[")"] → 0
["()"] → 2Go · 解法代码func longestValidParentheses(s string) int { st := []int{-1} // 栈底始终是"最后一个没能匹配的位置" best := 0 for i := 0; i < len(s); i++ { if s[i] == '(' { st = append(st, i) } else { st = st[:len(st)-1] // 尝试匹配：弹出一个左括号（或栈底） if len(st) == 0 { // 栈空了：这个右括号成为新的"栈底" st = append(st, i) } else if i-st[len(st)-1] > best { // 栈顶之后的一整段都是合法的 best = i - st[len(st)-1] } } } return best }
$ go build -o bin . && ./bin < cases.jsonl
["(()"] → 2
[")()())"] → 4
[""] → 0
["("] → 0
[")"] → 0
["()"] → 2JavaScript · 解法代码function longestValidParentheses(s) { const st = [-1]; // 栈底始终是"最后一个没能匹配的位置" let best = 0; for (let i = 0; i < s.length; i++) { if (s[i] === "(") { st.push(i); } else { st.pop(); // 尝试匹配：弹出一个左括号（或栈底） if (st.length === 0) st.push(i); // 栈空了：这个右括号成为新的"栈底" else best = Math.max(best, i - st[st.length - 1]); // 栈顶之后的一整段都是合法的 } } return best; }
$ node run.js < cases.jsonl
["(()"] → 2
[")()())"] → 4
[""] → 0
["("] → 0
[")"] → 0
["()"] → 2C++ · 解法代码#include <algorithm> #include <string> #include <vector> using namespace std; class Solution { public: int longestValidParentheses(string s) { vector<int> st = {-1}; // 栈底始终是"最后一个没能匹配的位置" int best = 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 best = max(best, i - st.back()); // 栈顶之后的一整段都是合法的 } } return best; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl
["(()"] → 2
[")()())"] → 4
[""] → 0
["("] → 0
[")"] → 0
["()"] → 2共 14 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 14/14 Java 通过 14/14 Go 通过 14/14 JavaScript 通过 14/14 C++ 通过 14/14
栈、动态规划、正反两次计数（O(1) 额外空间）、暴力，我在 20000 个随机括号串上验证了四种做法的答案，并在长度 1 万、10 万、100 万的随机括号串上测量了三种线性做法的耗时（每个取三次中最快）：
随机 20000 个长度 0 到 20 的括号串，栈 / 动态规划 / 正反两次计数 / 暴力四种做法答案全部一致：True 长度 n 的随机括号串上的耗时（三次中最快）： n= 10000: 栈 0.51 ms 动态规划 0.83 ms 正反两次计数 0.66 ms n= 100000: 栈 5.10 ms 动态规划 8.39 ms 正反两次计数 6.67 ms n= 1000000: 栈 51.45 ms 动态规划 84.70 ms 正反两次计数 67.87 ms
四种做法答案完全一致。三种线性做法的耗时都随长度线性增长，栈最快（100 万时 51.5ms），动态规划最慢（84.7ms），正反两次计数居中（67.9ms）。这只是 Python 里的实测，差别主要来自各自每一步的操作多少，不代表其他语言里的排序。
括号串是由 ( 和 ) 混合生成的，每个规模取三次中最快的一次：
字符串长度 n | 暴力解 | 本文解法
1000 | 10.668 ms | 0.038 ms
3000 | 104.399 ms | 0.121 ms
10000 | 1244.358 ms | 0.420 ms
30000 | （未测，太慢） | 1.236 ms暴力解从 1000 到 3000（3 倍）增长约 9.8 倍，从 3000 到 1 万增长约 11.9 倍，是平方增长；栈解法从 1000 到 30000（30 倍）增长约 32 倍，是线性增长。n = 1 万时暴力解 1244ms，栈解法 0.42ms，约 3000 倍。暴力解在 n = 3 万时没有再测。
Python 版本另外和暴力解做了随机对拍：
随机对拍 20000 组（长度 0 到 14 的随机括号串），solve 与 brute 的结果全部一致。
另外四种语言只在上面 14 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用 )(()())(。开头的 ) 没有 ( 可配，弹空栈后成为新的栈底 0；接着 (()()) 整段配对成功，长度 6；最后的 ( 一直留在栈里。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。