文章目录

leetcode32. 最长有效括号方法一：动态规划思路：代码：结果: 方法二：遍历两次思路：代码：结果：

leetcode32. 最长有效括号

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

示例 1:

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

示例 2:

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

---

方法一：动态规划

思路：

本题最暴力的方法就是枚举所有的子串，然后判断这个子串是否是有效的括号，维护最大长度的括号即可。这种想法的时间复杂度为O(N ^ 3)，枚举为O(N ^ 2)，判断还需要O(N)，不能通过。

因为在上面遍历过程中，需要很多的重复计算，所以我们使用动态规划的方法来解决。

我们维护一个dp数组，dp[i]表示**以s[i]为结尾的最长有效括号的长度。**我们可以知道，s中的左括号的位置，对应的dp值为0。

下面我们找状态转移方程，我们遍历s，忽略’(’，因为肯定为0，只考虑’)’：

如果s[i-1] = ‘(’，那么s[i-1]和s[i]构成了一个有效括号’()’，再加上dp[i-2]即可，即dp[i] = dp[i-2] + 2。如果s[i-1] = ‘)’，那么此时连续两个右括号，相当于这种情况'xxxx((。。。。。。))'，此时遍历到最后的’)’，内层是满足条件的，长度为dp[i-1]，需要看这个dp[i-1]所对应的有效括号的前面一个字符，是不是’(’，如果是的话，这样就相当于在dp[i-1]外层加一层’()’，dp[i-1] + 2。同时还需要考虑xxx是不是有效括号，如果是的话也要加上，长度为dp[i-dp[i-1]-2]。 所以dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]

考虑边界条件，只需要把dp[0]置为0即可，因为s的第一个元素对应的肯定是无效的。

我们在填写dp的时候，不断维护保存dp的最大值，返回即可。

只遍历了一次，时间复杂度为O(N)。使用了一个dp数组，空间复杂度为O(N)。

代码：

class Solution: def longestValidParentheses(self, s: str) -> int: n = len(s) #初始化dp dp = [0 for _ in range(n)] res = 0 #只有一个符号，返回0 if n == 1: return 0 #开始填写dp数组 for i in range(1,n): #只考虑')'，因为'('对应的肯定为0 if s[i] == ')': #如果前一个是'(',即这两个符号时'()'，长度＋2 if s[i-1] == '(': dp[i] = dp[i-2] + 2 #res保存dp中的最大值 res = max(res,dp[i]) #如果前一个是')'，则需考虑其他情况 #相当于这种情况'xxxx((。。。。。。))',此时遍历到最后的')', #内层是满足条件的，dp[i-1],需要看这个dp[i-1]所对应的前面一个 #是不是'('，这样就相当于在dp[i-1]外层加一层'()'。 #同时还需要考虑xxx是不是合法括号，是的话也要加上 #dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2] else: #防止越界 if i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(': #这里只需判断i-dp[i-1]-1 >= 0，而不需要管i-dp[i-1]-2 #的原因是，如果i-dp[i-1]-1 == 0，那么后者为-1 #根据python的特性，且此时是按顺序填写dp的，初始值是0 #所以dp[-1]一定是0，不造成干扰，所以不需要再判断 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2] res = max(res,dp[i]) return res

结果:

方法二：遍历两次

思路：

这种方法我们考虑到leetcode22题括号生成的方法。 leetcode22. 括号生成（Python3） 有效的括号字符串，那么它的左右括号的数量相等，且从左到右遍历这个字符串的时候，左括号的数量一直大于等于右括号的数量。

所以我们遍历s，初始化两个变量left_num、right_num保存遍历到的左右括号数，

当left_num = right_num时，此时一个有效括号长度为2 * left_num，更新res，继续遍历…当遇到left_num < right_num时，此时无效了，重新将left_num和right_num初始化为0，继续遍历。

上面的方法有一种情况无法处理，比如'((())'这种情况，**因为left_num一直大于right_num，所以无法找到后面长度为4的答案。**而如果从右向左遍历，则可以找到，所以我们再从右向左遍历一次，

从右向左遍历的时候，右括号的数量需要一直大于等于左括号数量。所以我们重新初始化两个变量，从右向左遍历，

当left_num = right_num时，此时一个有效括号长度为2 * left_num，更新res，继续遍历…当遇到left_num > right_num时，此时无效了，重新将left_num和right_num初始化为0，继续遍历。

我们可以看到，从右向左遍历的时候，比如'(()))'这种情况无法处理，而从左向右遍历可以处理。因此两次遍历可以将这些情况都考虑在内。最后返回res即可。

遍历两次，时间复杂度为O(2N)，渐进时间复杂度为O(N)。只使用了几个变量，空间复杂度为O(1)。

代码：

class Solution: def longestValidParentheses(self, s: str) -> int: left_num = 0 right_num = 0 n = len(s) res = 0 #从左到右遍历一次 for i in range(n): if s[i] == '(': left_num += 1 else: right_num += 1 if left_num == right_num: res = max(res,2*left_num) elif left_num < right_num: left_num = right_num = 0 left_num = 0 right_num = 0 #从右向左遍历一次 for i in range(n-1,-1,-1): if s[i] == '(': left_num += 1 else: right_num += 1 if left_num == right_num: res = max(res,2*left_num) elif left_num > right_num: left_num = right_num = 0 return res

结果：