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
                
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容