32. 最长有效括号(困难）-动态规划

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度

分析

• 第一想法想到的是栈，但是也有一些陷阱要注意
• 就是需要弹出后再考虑长度更新，另外需要考虑到栈为空的时候
• 方案二是动态规划，但是比较难想，就是当前为“)"去寻找最大长度，分成两部分，一部分是上一个也是(, 另一个上一个是")"，但是也有可能之前更远还有能匹配的括号
• 方案三是技巧，要非常熟悉括号的规律，以从左到右为例，如果要最大长度，那么最大的长度就是有效右扩号的两倍，另外也需要考虑从右到左再做一次

方案一

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 往前遍历，如果碰到")"，就判断栈的最后一位是不是"(", 如果是"(", 则消除并判断，如果是")", 则压入

        n = len(s)

        max_len = 0

        # 初始化第一位，因为这个涉及到有可能有"()"这样的，弹出后，下一个就是空的，或者下面特别处理也行
        #stack = [(")", -1)]
        stack = []

        for i in range(n):
            if s[i] == "(":
                stack.append((s[i],i))
            else:
                if stack and stack[-1][0] == "(":
                    # pop需要放到第一位，因为需要找到弹出后的后面那一位才是最远的索引
                    stack.pop()
                    if not stack:
                        max_len = max(max_len, i + 1)
                    else:
                        max_len = max(max_len, i - stack[-1][-1])
                    
                else:
                    stack.append((s[i],i))
        
        return max_len

方案二

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 动态规划，这个有点难想，当时也可以熟悉动态规划的过程

        n = len(s)
        # 这个定义是以i为结束的括号子串的最大长度
        dp = [0]*n
        max_res = 0
        for i in range(1, n):
            if s[i] == ")":
                if s[i - 1] == "(":
                    dp[i] = 2 + (dp[i - 2] if i > 2 else 0)
                elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == "(":
                    dp[i] = dp[i - 1] + 2 + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] - 2 >= 0 else 0 )
                max_res = max(max_res, dp[i])
        # 有时候是用最大，有时候才是最后       
        return max_res

方案三

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # 还有一个就感觉有点技巧了，是比较了解括号的规律，
        # 最大长度窗口肯定是在右括号等于左括号时出现
        # 有个问题就是如果只是从左到右，有可能右括号永远不会可以左括号一样，所以可以反过来再做一次

        left, right, n = 0, 0, len(s)
        max_res = 0
        for i in range(n):
            if s[i] == "(":
                left += 1
            else:
                right += 1
            
            if left == right :
                max_res = max(max_res, right * 2)
            elif right > left:
                left, right = 0, 0
        # 陷阱1，需要重新初始化left和right
        left, right = 0, 0
        for i in range(n - 1, -1, -1):
            if s[i] == ")":
                right += 1
            else:
                left += 1
            
            if left == right:
                max_res = max(max_res, left * 2)
            elif left > right:
                right, left = 0, 0

        
        return max_res