32. Longest Valid Parentheses

【Description】

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

Example 1:
Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"

Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

【Idea】

之前做过类似的括号对判断，核心基本是：
遇左括号进栈，遇右括号出（同时根据题干加一些options）

【Solution】

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        output = 0
        temp_max = 0
        stack = [0]      # stack[0]存储当前遍历的子串中匹配的括号对长度。一旦不符， 则置零（同时注意比较longest）重新计算。index=1,2,3……的值用来存储当前的最长括号对长度
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(0)
            else:
                if len(stack) > 1:
                    val = stack.pop()
                    stack[-1] += val + 2
                    output = max(stack[-1], output)  
                else:
                    stack = [0]
        return output