链接：最长有效括号
动态规划
dp[i]表示以第i个字符结尾的最长有效括号的长度，如果s[i]是左括弧，则肯定不是有效括号，dp[i]=0。对于s[i]=='0'，dp[i]的计算方法如下
- 判断下标
是否大于等于0，如果
或者s[j] !='('，则dp[i]=0
2.如果下标
第一项2是因为第i个和第j个位置构成一对有效括号。是内部有效括号的长度。
是第j位前面的外部有效括号长度，如果
的话，外部有效括号长度为0。
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s:
return 0
dp = [0] * len(s)
for i in range(len(s)):
if s[i] == '(':
dp[i] = 0
else:
if i-1 >= 0 and i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
dp[i] = 2 + dp[i-1]
if i-dp[i-1]-2 >= 0:
dp[i] += dp[i-dp[i-1]-2]
else:
dp[i] = 0
return max(dp)
栈
这题使用栈的关键是，在栈顶保持上个没有被匹配的右括号的下标。
在遍历字符串时，遇到左括弧，将下标入栈；遇到右括号，先将栈顶元素出栈，然后分析栈的情况：
- 如果栈不为空，也就是现在栈顶至少还有一个右括号的下标，则这轮中出栈的肯定是左括号，和当前遍历到的右括号匹配。
- 如果栈为空，说明我们当前遍历的的右括号是一个新的不能匹配的右括号，这时将当前下标入栈，即可维持栈底是上个没有被匹配的右括号下标的性质。
初始化栈时需要放入一个-1。
class Solution:
def longestValidParentheses(self, s: str) -> int:
max_length = 0
stack = [-1]
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if stack:
length = i - stack[-1]
max_length = max(length, max_length)
else:
stack.append(i)
return max_length
正反遍历法
使用两个遍历left、right分别记录遍历过程中遇到到左括号、右括号的个数。
首先从左往右遍历，如果遍历完某个字符后，，说明左右括号刚好匹配，这时更新最大长度
，如果
说明出现了不能匹配的右括号，这时候将left、right都置为0。
这中方法会出现中间有未匹配的左括号，导致结果小，需要在从右往左在遍历一次，其他操作都不变，就是这次如果就将left、right都置为0。
class Solution:
def longestValidParentheses(self, s: str) -> int:
left, right = 0, 0
max_length = 0
for c in s:
if c == '(':
left += 1
else:
right += 1
if left == right:
max_length = max(max_length, left+right)
elif right > left:
left, right = 0, 0
left, right = 0, 0
for c in reversed(s):
if c == '(':
left += 1
else:
right += 1
if left == right:
max_length = max(max_length, left+right)
elif left > right:
left, right = 0, 0
return max_length
