32. Longest Valid Parentheses

题目

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.

题意和思路

题意：在一个字符串中找出最大的满足连续括号匹配的个数
思路：将没有匹配的括号的下标记录下来，在它们之间的差值中找出最大值即可

python实现

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        st=[]
        
        res=0
        
        for i in xrange(len(s)):
            if not st or (ord(s[i])-ord(s[st[-1]]))!=1:
                st.append(i)
            else:
                st.pop()
        
                    
        n=len(s)
        if not st:
            return n
        a=n
        while st:
            b=st.pop()
            res=max(res,a-b-1)
            a=b
        res=max(res,a)            
        return res

补充

其实我这道题AC不是用的上面的思路，而是一种极为复杂的思路：
遍历s，对于字符’(‘，则进栈；对于字符’)’，判断前一个字符是否为’(‘，如果是则length+2，如果不是则让栈空，判断length和maxlength大小，并清空i；然后返回length和maxlength中的最大值
当然肯定没有通过
于是我对栈继续判断，栈中的情况只可能是空或者有多余的‘(‘对应的下标，然后对下标做处理，有这么几种情况：

最大值匹配的最后一个括号的下标小于栈中第一个’(‘对应的下标
最大值匹配的最后一个下标大于栈中第一个‘(’对应的下标

对于第1种情况，直接返回最大值即可
对于第2种情况，是这么处理的，计算栈中’(‘与‘(’下标之间的长度，并将最大值减去栈中所有长度的和sum，将其和栈中的长度lengthi相比，选取最大值返回(因为从第一个’(‘开始，对于最大值的增加都是不应该的)
这样有一个问题：假设最大值maxlength的前一个最大值maxpre，肯定有maxlength>maxpre，但是因为栈不为空，说明maxlength肯定多加了，而且满足第2种情况，于是按照上面的做法发现maxlength-sum后仍然比其中的lengthi都要大，但是却小于maxpre,上面返回的是maxlength-sum，但是实际上确实maxpre,因此在第二种情况返回时，需要取maxpre和maxlength-sum的最大值
代码如下，供参考：

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack=[]
        length=0
        maxlength=0
        maxindex=0
        maxpre=0
        index_list=[]
        i=-1
        for j in range(len(s)):
            index_list.append(0)
            if s[j]=='(':
                i+=1
                stack.append(s[j])
                index_list[i]=j
            else:
                if i>=0 and stack[i]=='(':
                    length+=2
                    i-=1
                else:
                    stack=[]
                    i=-1
                    if length>maxlength:
                        maxlength=length
                        maxindex=j
                        maxpre=maxlength
                    length=0
            j+=1
        if maxlength<length:
            maxlength=length
            maxindex=len(s)
        if i>=0 and maxlength!=0 and index_list[i]<maxindex:
            index_list[i+1]=len(s)
            for j in range(i+1):
                length=index_list[j+1]-index_list[j]-1
                index_list[j]=length
            length=0
            sum=0
            for j in range(i+1):
                sum+=index_list[j]
                if index_list[j]>length:
                    length=index_list[j]
            maxlength=maxlength-sum if maxlength-sum>length else length
        return max(maxlength,maxpre)

启发

以后做算法题，可不能往复杂的想了，各种问题，幸好leetcode有很多示例，不然都不知道哪错了，做算法题思路一定要清晰，简洁