Description

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.

Subscribe to see which companies asked this question

Note: The longest vaild parentheses is a substring of s

My Solution:

思路： 1. 创建两个栈，一个用来放字符，一个用来放字符对应的索引，为了防止栈为空分别加入‘)’，0, 2.遍历字符串，如果当前的字符串的字符为‘)’并且字符栈中的最上面为的字符为‘（’，这样意味着即将匹配成功，就把栈顶的字符pop出去（可以看成是先把当前的字符压栈，再pop出去一对），否则压栈，并把对应字符的索引压到另外一个数据栈。 3.生成一个索引的list，可以发现，留下来的数据之间和匹配成功的对数有关系，即两两之间的差减一，然后就可以找到最大值