leetcode——32. 最长有效括号

这道题我还是没思路，看了别人的做法觉得豁然开朗简单明了！！！！

栈：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        res=[]
        stack=[]
        for i in range(len(s)):
            if stack and s[i]==')':
                res.append(stack.pop())
                res.append(i)
            if s[i]=='(':
                stack.append(i)
        res.sort()
        i=0
        ans=0
        n=len(res)
        while i<n:
            j=i
            while j+1<n and res[j+1]==res[j]+1:
                j+=1
            ans=max(ans,j-i+1)
            i=j+1
        return ans

执行用时 :88 ms, 在所有 python3 提交中击败了26.32%的用户

内存消耗 :14.5 MB, 在所有 python3 提交中击败了8.33%的用户

 

方法2：

动态规划：

题解讲得真清晰：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n=len(s)
        if n==0:return 0
        dp=[0]*n
        res=0
        for i in range(n):
            if i>0 and s[i]==')':
                if s[i-1]=='(':
                    dp[i]=dp[i-2]+2
                elif s[i-1]==')' and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=='(':
                    dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]
                if dp[i]>res:
                    res=dp[i]
        return res    

执行用时 :48 ms, 在所有 python3 提交中击败了98.93%的用户

内存消耗 :13.8 MB, 在所有 python3 提交中击败了46.97%的用户

 

                                                                                    ——2019.10.17