32. longest-valid-parentheses 最长有效括号
难度: 困难
刷题内容
原题连接
- https://leetcode.com/problems/longest-valid-parentheses
- https://leetcode-cn.com/problems/longest-valid-parentheses
内容描述
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
解题方案
思路 1
- 动态规划，参考banananana
- 用一个
dp数组来存放以每个index为结尾的最长有效括号子串长度，例如：dp[3] = 2代表以index为3结尾的最长有效括号子串长度为2 - 很明显
dp[i]和dp[i-1]之间是有关系的 - 当
s[i] == ‘(’时，dp[i]显然为0, 由于我们初始化dp的时候就全部设为0了，所以这种情况压根不用写 - 当
s[i] == ')'时， 如果在dp[i-1]的所表示的最长有效括号子串之前还有一个'('与s[i]对应，那么dp[i] = dp[i-1] + 2, 并且还可以继续往前追溯（如果前面还能连起来的话)
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0:
return 0
dp = [0 for i in range(len(s))]
for i in range(1, len(s)):
if s[i] == ')':
left = i - 1 - dp[i-1]
if left >= 0 and s[left] == '(':
dp[i] = dp[i-1] + 2
if left > 0: # 这个是判断 left 前面是否能与后面继续连起来
dp[i] += dp[left-1]
return max(dp)
思路 2
每当遇到一个左括号或者是无法成对的右括号，就将它压入栈中，可以成对的括号则从栈中 pop 出。这样栈中剩下的就是无法成对的括号的下标。这时我们可以判断这些下标间的距离来获得最大的成对括号长度。 在这里，我们需要先遍历一遍字符串，再遍历一下非空的堆栈。一定要注意，这里我们遍历的非空的栈存储的是没有匹配上的括号下标，匹配上的我们都已经做了pop 处理。
class Solution(object):
def longestValidParentheses(self, s):
"""
:type s: str
:rtype: int
"""
stack = []
for i in range(len(s)):
if s[i] == ')':
if stack and s[stack[-1]] == '(': ## 这里要注意，不能想当然地用s[i-1]，因为我们有些下标直接continue了没有存到栈中去
stack.pop()
continue
stack.append(i)
max_length = 0
next_index = len(s)
while stack:
cur_index = stack.pop()
cur_length = next_index - cur_index - 1
max_length = max(cur_length, max_length)
next_index = cur_index
return max(next_index, max_length)
