LeetCode 32. 最长有效括号（难）

使用了两个变量 Left 和 Right，分别用来记录到当前位置时左括号和右括号的出现次数。
当遇到左括号时，Left 自增 1，右括号时 Right 自增1。
对于最长有效的括号的子串，一定是左括号等于右括号的情况，此时就可以更新结果 res 了，一旦右括号数量超过左括号数量了，说明当前位置不能组成合法括号子串，Left 和 Right 重置为 0。

题目

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

示例

示例 1: 

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

示例 2: 

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

考察知识点

字符串、动态规划、栈

核心思想

看到括号匹配，第一反应就应该是栈。

方法一、常规方法

1、遇到开括号，入栈。
2、只要是遇到闭括号，不管三七二十一，先弹出栈。 3、遇到没有开括号匹配的的闭括号，入栈。

代码概述

0、做特判，s=""，直接返回0。
1、遇到‘（’，直接把对应的下标push到栈中；因为‘（’是不能匹配弹出字符的，括号只有右括号才能标识一个完整的括号喔！
2、遇到‘）’：
2.1、弹出栈顶的下标
2.2.1、检测栈是否为空，如果为空，代表该闭括号没有对应的开括号匹配，只要在此之前出现过开括号，栈就不可能为空。因为一开始栈就不为空，有一个-1在里面，然后一旦遇到开括号也会入栈，这样一旦前面出现过开括号，最起码也得有两个数字，2.1步骤弹出去一个，也还剩一个，不可能是空栈。所以，如果是空栈，那一定是之前从来没出现过开括号，即该闭括号无效，没有相应的开括号与之对应。 将当前‘)’的下标push进入栈中，然后continue；
2.2.2、栈不为空，说明，至少前面出现过开括号，该闭括号是效的。，先用当前‘）’的下标减去栈顶的下标，得到目前子串的长度count，与当前最大长度max_count比较，并存储大的数值在max_count中。

注意
初始化栈时，添加栈底元素-1，用来做边界条件，当输入的就是“()”时，‘)’在1号位置，此时弹出0号位置，的“(”，1-(-1)=2，才是正确的长度。；
遇到‘）’的时候，不论什么情况，首先需要pop栈顶元素。如果此时栈中没有元素，才记录自己的下标到栈底，这样时刻保持了最多最多只有only1个‘）’在栈中(当然存储的是它的下标)。

方法二、动态规划

0.我们用 dp[i] 表示以 i 结尾的最长有效括号；
1.当 s[i] 为 (,dp[i] 必然等于 0，因为不可能组成有效的括号；
2.那么 s[i] 为 )
2.1 当 s[i-1] 为 (，那么 dp[i] = dp[i-2] + 2；
2.2 当 s[i-1] 为 ) 并且 s[i-dp[i-1] - 1] 为 (，那么 dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]；
通过将一系列结果暂存在dp中，避免重复计算。

方法三、借助变量

使用了两个变量 Left 和 Right，分别用来记录到当前位置时左括号和右括号的出现次数。
当遇到左括号时，Left 自增 1，右括号时 Right 自增1。
对于最长有效的括号的子串，一定是左括号等于右括号的情况，此时就可以更新结果 res 了，一旦右括号数量超过左括号数量了，说明当前位置不能组成合法括号子串，Left 和 Right 重置为 0。
但是对于这种情况 "(()" 时，在遍历结束时左右子括号数都不相等，此时没法更新结果 res，但其实正确答案是 2，怎么处理这种情况呢？

答案是再 反向遍历一遍 ，采取类似的机制，稍有不同的是此时若 Left 大于 Right 了，则重置 0，这样就可以涵盖所有情况。

五分钟学算法

Python版本

方法一的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0: return 0
        dp = [0] * n
        res = 0
        for i in range(n):
            if i>0 and s[i] == ")":
                if  s[i - 1] == "(":
                    dp[i] = dp[i - 2] + 2
                elif s[i - 1] == ")" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
                if dp[i] > res:
                    res = dp[i]
        return res

print("leet code accept!!!")
Input = [")(()())", "(()", ")()())"]
Input1 = []
Answer = [6, 2, 4]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.longestValidParentheses(Input[i])
        print(result==Answer[i])

时间复杂度\(O(n)\)

递归方法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n == 0: return 0
        dp = [0] * n
        res = 0
        for i in range(n):
            if i>0 and s[i] == ")":
                if  s[i - 1] == "(":
                    dp[i] = dp[i - 2] + 2
                elif s[i - 1] == ")" and i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
                    dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2]
                if dp[i] > res:
                    res = dp[i]
        return res

时间复杂度\(O(n)\)

方法三的实现

借助额外的常数级别的存储空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0

        left = 0
        right = 0
        maxlength = 0

        i = 0
        while i < len(s):
            if s[i] == '(':
                left += 1
            else:
                right += 1
            
            if left == right:
                maxlength = max(maxlength, 2*right)
            elif right >= left:
                left = right = 0
            i += 1

        left = right = 0
        i = len(s)-1
        while i >= 0:
            if s[i] == '(':
                left += 1
            else:
                right += 1
            
            if left == right:
                maxlength = max(maxlength, 2*right)
            elif left >= right:  # 反向这之后，这里的条件和上面有所不同。
                left = right = 0
            i -= 1
        
        return maxlength