[LeetCode]题解（python）：032-Longest Valid Parentheses

题目来源

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

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

题意分析

Input：str

Output：length

Conditions：返回最长有效子串

　　　　　　有效：符合括号匹配规律

题目思路

用一个list存储左括号‘（’的位置（index），用一个变量last（起始值为0）存储某一个有效字串的开始（last不断更新），用maxlength存储全局最大长度，如果遇到右括号‘）’，

如果此时list为空，表示没有左括号与之匹配，此时length = i - last；同时更新last = i + 1（表示last之前的串没用了），将list置为空；
如果list不为空，说明可以消除，则list.pop()，pop完之后，如果list为空，说明在last之后的串都符合，length = i + 1 - last；如果list不为空，则说明list最后一个位置之后的串都符合，length = i - L[-1]
根据length与maxlength大小持续更新maxlength

AC代码（Python）

 1 class Solution(object):
 2     def longestValidParentheses(self, s):
 3         """
 4         :type s: str
 5         :rtype: int
 6         """
 7         maxlength = 0
 8         L = []
 9         last = 0
10         if len(s) == 0:
11             return 0
12         for i in range(len(s)):
13             #print(len(s),len(L))
14             if s[i] == '(':
15                 L.append(i)
16             elif s[i] == ')':
17                 if len(L) == 0:
18                     length = i - last
19                     L = []
20                     last = i + 1
21                     if length > maxlength:
22                         maxlength = length
23 
24                 else:
25                     L.pop()
26                     if len(L) == 0:
27                         length = i + 1 - last
28                     else:
29                         length = i - L[-1]
30                     if length > maxlength:
31                         maxlength = length
32         
33         return maxlength

View Code