Longest Valid Parentheses
给你一个只由 ( 和 ) 组成的字符串 s。找出其中最长的格式正确的子字符串（连续的一段字符）：其中每个 ( 都由后面的 ) 闭合，并且括号正确嵌套，如 (()())。返回该子字符串的长度；如果连 () 都没有出现，则返回 0。
函数
- sstring
- 由 ( 和 ) 字符组成的字符串
- 返回值integer
- 最长格式正确子串的长度；如果不存在，则为 0
约束条件
1 ≤ s.length ≤ 6 × 104- 字符串
s中的每个字符都是(或)。
示例
- 输入
- s = "()(())"
- 输出
- 6
- 解释
- 整个字符串的格式都正确：
()后面跟着(())。两个格式正确的部分并排放在一起，就组成一个完整的字符串，所以答案是全部 6 个字符。
- 输入
- s = "())((())"
- 输出
- 4
- 解释
- 索引 2 处的
)没有配对项，因此没有答案会跨过它，而索引 3 处的(始终没有闭合。最长的片段是索引 4 到 7 处的(())，长度为 4，比开头的()更长。
- 输入
- s = "))(("
- 输出
- 0
- 解释
- 两个
)都出现在两个(之前，所以没有任何(被闭合，答案是 0。
进阶
你还可以报告最长的格式正确子字符串从哪里开始吗？如果有多个子字符串长度相同，请选择最靠左的那个。
提示
逐个打开提示，每个都会多透露一点。
从左向右读取一个子字符串，并维护一个计数：遇到
(时加 1，遇到)时减 1。在格式正确的子字符串中，计数会怎样变化？如果某个)让计数降到零以下，这说明所有跨过它的子字符串有什么问题？用一个栈保存仍未闭合的
(字符的索引。当)闭合栈顶的字符时，到此结束的格式正确的连续子串从此时栈顶剩余索引的后一位开始。当没有未闭合的字符时，栈中应该放什么？将栈的初始值设为 -1，也就是字符串前一个位置的索引。每遇到一个
(，就将它的索引压入栈中。遇到)时，弹出栈顶元素；如果此时栈为空，说明这个)永远无法匹配，因此将它的索引压入栈中作为新的基准；否则，当前连续段的长度就是i减去栈顶索引。记录测得的最大连续段长度。
题解
格式正确的片段相邻时会连接起来，因此 () 和 (()) 并排放置会组成一段连续序列。一个多余的字符，比如 ())(()) 中的 )，会将字符串截断，因此没有连续序列能跨过它。用带基准标记的索引栈，可以在一次遍历中跟踪当前连续序列的起始位置；也可以通过两次计数器遍历完成，内存占用为 O(1)。
从每个起点扩展子字符串
结果正确，但无法在最大的测试中运行完毕
思路
固定一个起点，向右扫描并维护一个计数值：遇到 ( 加 1，遇到 ) 减 1。只有当计数值在不低于 0 的情况下回到 0 时，这段序列才是合法的，因此每次计数值回到 0 时都记录它的长度。计数值低于 0 时就停止：从这个起点开始的任何更长序列中，这个 ) 都会保持未匹配状态。
在 59998 个 ( 后面接着 () 的情况下，每个起点都会扫描到末尾：对于 n = 6 × 10^4，大约需要 n²/2 = 1.8 × 10^9 步。
算法
- 将
best设为 0。 - 对于每个起始位置，将
balance设为 0，然后从起始位置开始遍历，到最后一个字符结束。 - 遇到
(时加 1，遇到)时减 1。 - 如果
balance小于 0，就停止处理这个起始位置。如果它等于 0，就用end - start + 1更新best。 - 返回
best。
def longestValidParentheses(s):
best = 0
for start in range(len(s)):
balance = 0
for end in range(start, len(s)):
balance += 1 if s[end] == "(" else -1
if balance < 0:
# A ')' without a partner: no longer run starts here
break
if balance == 0:
best = max(best, end - start + 1)
return best带有基准标记的索引栈
思路
压入索引，并在栈底多保留一个索引：基准，也就是当前连续段之前的位置，起始时为 -1。遇到 ( 时，压入它的索引。遇到 ) 时，弹出一个索引。如果此时栈为空，说明你弹出的是基准：这个 ) 无法与任何括号配对，因此它的索引会成为新的基准。否则，栈顶就是以 i 结尾的连续段中最后一个字符之前的位置，它可能是一个左括号 (，也可能是基准，因此连续段的长度是 i - top。
基准可以把相邻的片段连接起来。对于 ()(())，最后一个 ) 会弹出索引 2，并发现栈顶是 -1：5 - (-1) = 6。对于 ())((())，索引 2 会弹出基准，并成为新的基准；最后一个 ) 会弹出索引 4，并发现栈顶是索引 3 处的左括号 (：7 - 3 = 4。
每个索引最多压入和弹出一次：时间复杂度为 O(n)。
算法
- 创建一个初始值为 -1 的栈，并将
best设为 0。 - 对于每个索引
i，如果s[i]是(，就将i入栈。 - 如果是
)，就弹出一次。 - 如果此时栈为空，就将
i入栈作为新的基准。否则，用i - top更新best。 - 返回
best。
def longestValidParentheses(s):
# The bottom of the stack is the index just before the current run
stack = [-1]
best = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack:
# This ')' has no partner: it becomes the new base
stack.append(i)
else:
best = max(best, i - stack[-1])
return best分两次遍历统计开括号和闭括号
思路
从左向右遍历，统计上次重置后出现的 opens 和 closes。计数相等表示重置后的一切都格式正确，长度为 2 × closes。当 closes 超过 opens 时，某个 ) 没有配对项，因此重置两者。永远没有对应右括号的 ( 会让 opens 一直领先，所以对于 (()，这一遍找不到任何结果。再从右向左遍历，在 opens 超过 closes 时重置，并保留较大的答案。
遍历两遍就够了。最长连续段会被无法匹配的字符或字符串两端截断。如果它左侧的边界是一个多余的 )，或者就是字符串开头，第一遍会在连续段的起点重置。如果它左侧的边界是一个多余的 (，那么它右侧的边界就不可能是 )，因为那样会与这个 ( 配对并延长连续段，所以第二遍能够找到它。
算法
- 将
best、opens和closes设为 0。 - 从左向右遍历，统计每个字符。当计数相等时，用
2 × closes更新best。当closes较大时，将两者都重置为 0。 - 重置两个计数器，然后用相同的方法从右向左遍历，当
opens较大时重置计数器。 - 返回
best。
def longestValidParentheses(s):
best = 0
# Left to right: more ')' than '(' ends every run that started earlier
opens = closes = 0
for ch in s:
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * closes)
elif closes > opens:
opens = closes = 0
# Right to left: catches the runs that an unmatched '(' hid from the first pass
opens = closes = 0
for ch in reversed(s):
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * opens)
elif opens > closes:
opens = closes = 0
return best
易错点和边界情况
- 统计整个字符串中的匹配对数。
())((())有 3 对，但它们并非全部相连，所以答案是 4，而不是 6。 - 从匹配的
(开始测量连续长度。对于()(())，最后一个)与索引 2 匹配，得到 4，却漏掉了前面的()。 - 从空栈开始，而不是从基准值 -1 开始（Lua 和 R 中是 0，因为它们的位置从 1 开始）。这样，
())中的第一个)就没有可供比较的位置。 - 只朝一个方向运行计数器。从左到右处理
(()会返回 0，从右到左处理())也会返回 0；两者的答案都是 2。 - 计数器相等时重置。连续长度仍可能继续增长，例如
()()。
常见问题3
最长有效括号的时间复杂度是多少？
栈解法和两遍计数解法的运行时间都是 O(n)。最坏情况下，栈需要 O(n) 的内存，例如字符串中只有 (；而计数器只需要 O(1) 的内存。尝试每个起始位置的时间复杂度是 O(n²)。
最长有效括号问题有动态规划解法吗？
是的。令 end[i] 表示以 i 结尾的最长有效括号序列长度，当 s[i] 为 ( 时，其值为 0。如果 s[i-1] 为 (，则 end[i] = end[i-2] + 2。否则，令 j = i - end[i-1] - 1；如果 s[j] 为 (，则 end[i] = end[i-1] + 2 + end[j-1]。最大的 end[i] 就是答案。
这与有效的括号有什么不同？
Valid Parentheses 要判断整个字符串是否格式正确，答案只有是或否，用一个计数器或栈就能回答。这里你要找的是最长的格式正确子字符串，因此还要记录每段的起始位置，并在遇到永远无法匹配的字符后重新开始。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def longestValidParentheses(s):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
s = "()(())"
预期输出
6