最长有效括号

题目描述方法一：栈思路代码复杂度分析 方法二：动态规划思路代码复杂度分析 方法三：无需额外空间思路代码复杂度分析

题目描述

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

示例 1: 输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()”

示例 2: 输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

示例 3: 输入: “())((())” 输出: 4 解释: 最长有效括号子串为 “(())”

方法一：栈

思路

始终保持栈底元素为当前已经遍历过的元素中==「最后一个没有被匹配的右括号的下标」==，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标： 需要注意的是，一开始的时候往栈中放入一个值为 -1 的元素，这样可以保证，在遇到“)”之后先出栈后栈为空时，将其索引入栈，从而保证「最后一个没有被匹配的右括号的下标」

对于遇到的每个‘(’ ，我们将它的下标放入栈中对于遇到的每个‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号，匹配之后，会遇到以下两种情况： 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的「最后一个没有被匹配的右括号的下标」，比如“())”，前两个匹配，当遍历到第二个右括号时，但遇到“)”均先pop，所以此时栈为空，需要把当前右括号的索引入栈，说明该括号不能匹配到；如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」，最终返回最大长度 我们从前往后遍历字符串并更新答案即可。

代码

class Solution: def longestValidParentheses(self, s: str) -> int: #一开始的时候往栈中放入一个值为 -1 的元素 stack = [-1] length,max_length=0,0 for i in range(len(s)): if s[i] == '(': stack.append(i) else: #遇到的每个‘)’先弹出栈顶元素,栈为空时，再将其入栈 stack.pop() if stack == []: stack.append(i) else: length = i-stack[-1] max_length = max(max_length,length) return max_length

复杂度分析

时间复杂度：O(n)，n 是给定字符串的长度。我们只需要遍历字符串一次即可。 空间复杂度： O(n)。栈的大小在最坏情况下会达到 n，因此空间复杂度为 O(n) 。

方法二：动态规划

思路

我们定义dp[i]表示以下标 i 字符结尾的最长有效括号的长度。我们将 dp 数组全部初始化为 0 。显然有效的子串一定以‘)’ 结尾，因此我们可以知道以‘(’ 结尾的子串对应的dp 值必定为 0 ，我们只需要求解 ‘)’ 在 dp 数组中对应位置的值。 我们从前往后遍历字符串求解 dp 值，我们每两个字符检查一次：

s[i]=‘)’ 且 s[i−1]=‘(’，也就是字符串形如 “……()”，我们可以推出： 我们可以进行这样的转移，是因为结束部分的 “()” 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2 。s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”，我们可以推出： 如果s[i−dp[i−1]−1]=‘(’，那么 最后的答案即为 dp 数组中的最大值。

代码

class Solution: def longestValidParentheses(self, s: str) -> int: n = len(s) if n==0:return 0 dp = [0]*n for i in range(len(s)): # i-dp[i-1]-1是与当前)对称的位置 if s[i]==')' and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=='(': dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2 return max(dp)

复杂度分析

时间复杂度： O(n)，其中 n 为字符串的长度。我们只需遍历整个字符串一次，即可将 dp 数组求出来。 空间复杂度： O(n)，我们需要一个大小为 n 的dp 数组。

方法三：无需额外空间

思路

在此方法中，我们利用两个计数器left 和right 。首先，我们从左到右遍历字符串，对于遇到的每个‘(’，增加left 计数器，对于遇到的每个 ‘)’ ，增加right 计数器。

每当left 计数器与right 计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串。当right 计数器比left 计数器大时，我们将left 和right 计数器同时变回 0。遍历结束后，left和right均要变回0，以便下次从右至左的遍历 这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符我们都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的。 解决的方法也很简单，我们只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：当left计数器比right计数器大时，我们将left 和right 计数器同时变回 0当left计数器与right计数器相等时，我们计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串 这样我们就能涵盖所有情况从而求解出答案。

代码

class Solution: def longestValidParentheses(self, s: str) -> int: left,right,max_length,n=0,0,0,len(s) for i in range(n): if s[i]=='(':left+=1 else:right+=1 if left==right:max_length=max(max_length,right*2) elif right>left:left=right=0 left=right=0 for j in range(n-1,-1,-1): if s[j]=='(':left+=1 else:right+=1 if left==right:max_length=max(max_length,left*2) elif left>right:left=right=0 return max_length

复杂度分析

时间复杂度： O(n)，其中 n 为字符串长度。我们只要正反遍历两边字符串即可。 空间复杂度： O(1)，我们只需要常数空间存放若干变量。