【leetcode】32. 最长有效括号
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"还有一种是“（）（（）”，这种的有效长度是2。
分析1：
用栈，使用栈进行操作，如果是左括号，直接入stack，如果右括号，如果stack里没有元素匹对，说明有效括号已经结束，更新起始位置，有元素匹对pop出一个左括号匹对，如果此时没了，不能保证不继续有效括号，所以根据当前的最长距离去更新maxlen，如果此时还有 则计算与栈顶的索引相减来计算长度。
# 使用栈
# 思路是左括号压入栈，如果遇到右括号，且上一个是左括号，则出栈。先保存了一个右括号我是用来做哨兵
#的……方便后面做判定
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
res = 0
stack = [(-1,'(')]
for i, val in enumerate(s):
# 当前加入的元素是')',且栈顶元素是'（'
if val == ')' and stack[-1][1] == '(':
stack.pop()
# 当前元素的（记录位置）下标已经弹出栈时，栈顶元素的位置
# 即为最长有效括号
res = max(res,i-stack[-1][0])
else:
stack.append((i, val))
# print(stack)
return res分析2：
dp[i]为第i个位置的最长有效括号的长度。
- “()”:
dp[i] = dp[i - 2] + 2 #直接在历史匹配数上增加2
2.“))”:
if i - dp[i-1] - 1 >= 0: # 确保没有超出索引，对应最长括号的起始点
if s[i - dp[i - 1] - 1] == "(": #最后一个“)”是否有匹配
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2 # 在历史匹配上增加2代码：
def dpSolution(self,s):
n = len(s)
if n<2: return 0
# dp[i]表示第i个位置的最长有效长度
dp = [0]*n
res = 0
for i in range(1,n):
if s[i]==')' and s[i-1]=='(':
# 在历史匹配数上+2
dp[i]=dp[i-2]+2
if s[i]==')' and s[i-1]==')':
# 当前i的对称点索引是否存在
if i-dp[i-1]-1>=0:
if s[i-dp[i-1]-1]=='(':
dp[i] = dp[i-1]+dp[i-dp[i-1]-2]+2
# print(dp)
return max(dp)一些注释帮助理解：
参考：