题目描述
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号
子串
的长度。
示例 1:
输入:s = "(()" 输出:2 解释:最长有效括号子串是 "()"
示例 2:
输入:s = ")()())" 输出:4 解释:最长有效括号子串是 "()()"
示例 3:
输入:s = "" 输出:0
思路
一般括号问题都需要一个辅助栈
1)遍历字符串,如果是左括号,就直接入栈;如果是右括号且栈里已经有括号了,说明已经有成对的括号出现了;将栈的顶部括号pop出来,当前的也放入res数组里
2)对res数组进行排序
3)接下来,在res数组里,找到最长的连续升序,即为所求
class Solution(object):def longestValidParentheses(self, s):""":type s: str:rtype: int"""if not s:return 0stack = []res = []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 = 0ans = 0n = len(res)while i<n:j=iwhile j<n-1 and res[j+1] == res[j]+1:j+=1ans = max(ans, j-i+1)i = j+1return ansif __name__ == '__main__':s = Solution()ss = "()(()"print(s.longestValidParentheses(ss))