问题描述
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For "(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.
问题分析
hard题老不会，参考了九章算法，宝宝好伤心T.T
匹配问题考虑用栈。遇到“（”则入栈，遇到“）”时，如果栈空则表明不能匹配，从下一位置重新开始；如果栈非空则该“）”匹配栈顶“（”，要求当前匹配的长度，需要考虑：
- 当前栈顶为空，匹配长度为累积匹配长度+此次匹配长度；
- 当前栈顶不为空，匹配长度为当前匹配位置减去栈顶元素。
并不好理解...下面举个栗子：
给定字符串为“（）（（））”:
i=0，“（”入栈，stack=[0]；
i=1，“）”匹配，j=stack.pop()=0，此时栈空，匹配长度=累积长度+此次匹配长度=0+2=2，累积长度=2，最长匹配为2；
i=2，“（”入栈，stack=[2]；
i=3，“（”入栈，stack=[2, 3]；
i=4，“）”匹配，j=stack.pop()=2，此时栈非空，匹配长度=i-j=2；
i=5，“）”匹配，j=stack.pop()=4，此时栈空，匹配长度=累积长度+此次匹配长度=2+4=6，累积长度=6，最长匹配为6，匹配结束。
AC代码
#encoding=utf-8
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack = []
ac = 0
match = 0
m = 0
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
if len(stack) == 0:
ac = 0
match = 0
else:
j = stack.pop()
match = i - j + 1
#如果栈空，则需要累积匹配长度
if len(stack) == 0:
ac += match
match =
#若栈非空，栈顶元素后一位到此次匹配位置均匹配成功
else:
match = i - stack[-1]
if match > m:
m = match
return m
Runtime: 76 ms, which beats 79.94% of Python submissions.
