分类：String
考察知识点：String
最优解时间复杂度：O(n)
最优解空间复杂度：O(n)
32. Longest Valid Parentheses
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
代码：
stack方法:
class Solution:
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack=[]
start=-1
res=0
for i,ch in enumerate(s):
if ch=="(":
stack.append(i)
else:
if len(stack)==0:
start=i
else:
stack.pop()
if len(stack)==0:
res=max(res,i-start)
else:
res=max(res,i-stack[-1])
return res
讨论：
1.这道题有两种做法，一种stack一种DP
2.凡是看见括号的题目脑子里就一定要想到stack！！！
3.DP方法非到万不得已不要去用，不仅很难想，状态转移很难，而且很容易错
4.start是指前-后+1的（后+1）的部分，可以这么理解
加油
