[LeetCode]32 最长有效括号

题目描述

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack = []  
        start = 0   
        res = 0    
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                if not stack:
                    res = max(res, i-start)
                    start = i+1
                    continue
                else:
                    stack.pop()
                    if not stack:
                        res = max(res, i-start+1)
                    if stack:
                        res = max(res, i-stack[-1])
        return res