32 Longest Valid Parentheses

https://leetcode.com/problems/longest-valid-parentheses/

solution

• 动态规划

  • 以s[i]结尾的字符串能够构成的最长的匹配串的长度

# https://zhuanlan.zhihu.com/p/110240060

时间复杂度：O() 空间复杂度：O()

• 经典做法

  • 一个栈维护左括号的下标，然后遇到匹配的右括号时弹出左括号并通过下标计算长度

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        max_len = 0
        stack = [-1]
        for i in range(len(s)):
            
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        return max_len        

follow op

括号类小结