难度: Hard
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()" 输出：2 解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()"
示例 3：
输入：s = "" 输出：0
提示：
0 <= s.length <= 3 * 104s[i]为'('或')'
Submission
运行时间: 28 ms
内存: 15 MB
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = []
j = -1 # j+1是上一个最长有效括号的开始索引
ans = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
if stack:
stack.pop()
top = stack[-1] if stack else j # 如果栈内还有多余的(，如(()，top取该(的索引，否则如)(())，取j
ans = max(ans, i - top)
else:
j = i
return ans
Explain
该题解使用栈来解决问题。遍历字符串，遇到左括号就将其索引入栈，遇到右括号则将栈顶元素出栈，并更新最长有效括号子串的长度。如果栈为空，则将当前索引 i 赋值给 j，表示上一个最长有效括号子串的结束位置。最后返回最长有效括号子串的长度。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = []
j = -1 # j+1是上一个最长有效括号的开始索引
ans = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i) # 将左括号的索引入栈
else:
if stack:
stack.pop() # 遇到右括号，将栈顶元素出栈
top = stack[-1] if stack else j # 如果栈内还有多余的(，如(()，top取该(的索引，否则如)(())，取j
ans = max(ans, i - top) # 更新最长有效括号子串的长度
else:
j = i # 如果栈为空，则将当前索引 i 赋值给 j，表示上一个最长有效括号子串的结束位置
return ans
Explore
在遇到右括号且栈为空的情况通常表示当前右括号没有对应的左括号与之匹配，因此这个右括号是无效的。将当前索引赋值给变量j，是为了更新后续有效括号子串的起始位置。此时，j表示最后一个无法被匹配的右括号的位置。这样，后续遇到有效的括号对时，可以正确地计算其长度，即从最后一个无效右括号后的位置开始计算。
如果栈中剩余了左括号的索引，这表示这些左括号没有对应的右括号与之匹配。在计算过程中，这些未匹配的左括号实际上限制了有效括号子串的起始位置。任何有效子串都不能包括这些未匹配的左括号，只能从它们之后的位置开始。因此，在计算有效括号长度时，这些左括号的位置会作为一个新的起点来计算长度，这可能导致有效括号子串的长度减少。
使用`i - top`计算方式是因为，当栈中的顶部元素（即最近一个匹配的左括号的索引）被弹出后，新的栈顶元素（如果存在）就表示当前考虑的右括号之前的最近一个未匹配的左括号的位置。因此，当前有效的括号子串是从栈顶元素的下一个位置开始，直到当前右括号的位置。这使得`i - top`成为计算当前有效子串长度的正确方法。如果栈为空，则使用j作为起始位置，因为这表示之前所有的括号都已匹配完毕，新的子串开始于最后一个未匹配右括号之后。
在代码中，当栈为空且遇到一个有效的右括号时，`top`变量需要指向一个合适的起点，以便计算有效括号子串的长度。在这种情况下，使用变量j作为新的起点，因为j已经被更新为最后一个无效的右括号的索引。因此，任何新的有效子串都应该从j的下一个位置开始计算。这样，`top`变在栈为空时使用j作为新的起点，确保了有效子串的长度能够正确计算，避免了包含之前无效的右括号在内的计算错误。