给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。 示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()” 解题思路 输入的“(”是否有与之对应的“)”,求最大有效括号长度 方法一：暴力解法 解题思路 1、括号都是成对出现的，最长有效括号数一定是偶数 2、依次遍历当前子串是否为有效子串（从大往小遍历） 3、直到出现符合的子串，返回子串长度 代码
class Solution: def longestValidParentheses(self, s: str) -> int: #定义函数判断是否为有效子串 def isValid(x): #用栈的方式实现 stack = [] for i in range(len(x)): #如果当前为左括号将其入栈 if x[i] == '(': stack.append('('); #如果当前为右括号，判断此时栈顶元素是否为左括号，是的话将其弹出， #如果不是则当前子串不是有效子串 elif stack!=[] and stack[-1] == '(': stack.pop(); else: return False #有效子串栈中元素括号是一一对应的，栈中元素一定为空 return stack==[] #主调函数 if len(s)<2:return 0 n = len(s) #判断n的奇偶性：若为奇数取其最大偶数n-1，若为偶数从n开始，每次遍历长度-2，到2 为止 for i in range(n if n%2==0 else n-1,0,-2): for j in range(n-i+1): #将其放入isValid的函数中 if isValid(s[j:j+i]): return i return 0方法二：动态规划 解题思路 1、定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。 2、将 dp 数组全部初始化为 0 。显然有效的子串一定以‘)’ 结尾，因此我们可以知道以 ‘(’ 结尾的子串对应的 dp 值必定为 0 ，我们只需要求解‘)’ 在 dp 数组中对应位置的值。 3、状态转移方程的推导（来源：力扣官解）
寻找与i对应的位置 状态转移方程 文字解释 代码
class Solution: def longestValidParentheses(self, s: str) -> int: n = len(s) if n==0:return 0 #初始化一个全0的dp数组 dp = [0]*n for i in range(len(s)): # i-dp[i-1]-1是与当前)对称的位置 if s[i]==')' and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=='(': #状态转移方程 dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2 return max(dp)方法三：栈 解题思路 1、始终保持栈底元素为当前已经遍历过的元素中「最后一个没有被匹配的右括号的下标」，即在一开始的时候往栈中放入一个值为 −1 的元素（如图）。 2、对于遇到的每个‘(’ ，我们将它的下标放入栈中 3、对于遇到的每个‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号： 如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」 4、如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」 5、依次遍历直到遍历到最后一个数 代码
class Solution: def longestValidParentheses(self, s: str) -> int: #建立一个栈，栈底元素为-1 stack = [-1] length = 0 max_length = 0 #遍历，如果是左括号，将下标放入栈中，如果不是弹出栈顶元素（即与之对应的右括号） for i in range(len(s)): if s[i] == '(': stack.append(i) else: stack.pop() #若栈为空，把最后一个没有被匹配的右括号的下标放入栈来更新 if stack == []: stack.append(i) #如果栈不为空，当前右括号的下标减去栈顶元素 else: length = i-stack[-1] #更新最大长度 max_length = max(max_length,length) return max_length方法四：正向逆向结合法 解题思路 1、利用两个计数器left 和 right 。 2、从左到右遍历字符串，对于遇到的每个‘(’，left +1，对于遇到的每个 ‘)’ ，right +1。 3、当left = right时，计算当前有效字符串的长度（2right），并且记录目前为止找到的最长子字符串。当right >left时，left 和 right 计数器同时变回 0。 4、从右向左遍历字符串，对于遇到的每个‘(’，left +1，对于遇到的每个 ‘)’ ，right +1。 当left = right时，计算当前有效字符串的长度（2left），当right<left时，left 和 right 计数器同时变回 0。
代码
lass Solution: def longestValidParentheses(self, s: str) -> int: n, left, right, maxlength = len(s), 0, 0, 0 #从左向右遍历 for i in range(n): if s[i] =='(': left+=1 else: right+=1 if left == right: maxlength = max(maxlength, 2 * right) elif right > left: left = right = 0 #从右向左遍历 left = right = 0 for i in range(n-1,-1,-1): if s[i] =='(': left+=1 else: right+=1 if left == right: maxlength = max(maxlength, 2 * left) elif right < left: left = right = 0 return maxlength