LeetCode——最长有效括号（更优化方法）

Bertha 。 2022-05-16 12:15 153阅读 0赞

昨天自己做出来了，然后在网上百度了下发现有更巧妙的方法，这里记录一下。

参考博客：[https://blog.csdn.net/renjiewen1995/article/details/51193746][https_blog.csdn.net_renjiewen1995_article_details_51193746]

先贴代码：

class Solution:
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            maxLen = 0
            lefts = []
            for index,ch in enumerate(s):
                if ch == ')' and len(lefts) !=0 and s[lefts[len(lefts)-1]] == '(':
                    lefts.pop()
                    if len(lefts) == 0:
                        maxLen = index+1 #因为栈里没有异常点，说明全部匹配成功，所以就是当前index+1
                    else:
                        if index - lefts[len(lefts)-1] > maxLen :#这里栈顶永远是最近的异常点
                            maxLen = index - lefts[len(lefts)-1]
                else:
                    lefts.append(index)
            return maxLen
    if __name__ =="__main__":
        res = Solution()
        #'(()()(((((((())))))))'
        print(res.longestValidParentheses(")()())()()("))
        pass

这位老哥将异常点压入栈中，每次遍历都会计算当前子串的长度，即上一个异常点后的子串长度。

为什么说栈顶永远是最近的异常点呢？因为异常点一旦压入栈中就永远不会出栈，所以每一次右括号匹配到左括号就会重新计算子串长度。

[https_blog.csdn.net_renjiewen1995_article_details_51193746]: https://blog.csdn.net/renjiewen1995/article/details/51193746

发表评论取消回复

表情：

评论列表（有 0 条评论，153人围观）

还没有评论，来说两句吧...

相关阅读

相关 DP：最长有效括号

DP：最长有效括号问题： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0c

Love The Way You Lie/ 2023年10月06日 16:51/ 0 赞/ 7 阅读

相关 leetcode 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()"

Dear 丶/ 2023年08月17日 15:43/ 0 赞/ 79 阅读

相关最长有效括号

最长有效括号 1、参考资料 https://leetcode-cn.com/problems/longest-valid-parentheses/ 2、题目要求

今天药忘吃喽~/ 2022年12月05日 10:00/ 0 赞/ 104 阅读

相关 32. 最长有效括号

[https://leetcode-cn.com/problems/longest-valid-parentheses/][https_leetcode-cn.com_prob

今天药忘吃喽~/ 2022年09月10日 11:27/ 0 赞/ 104 阅读

相关 LeetCode32. 最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。示例 1：输入：s = "(()" 输出：2 解释：最长有效括号子串

系统管理员/ 2022年09月08日 00:12/ 0 赞/ 113 阅读

相关 leetcode 32. Longest Valid Parentheses 最长有效括号长度

Given a string containing just the characters ‘(’ and ‘)’, find the length of the longes

旧城等待，/ 2022年06月09日 09:41/ 0 赞/ 137 阅读

相关 LeetCode——最长有效括号（更优化方法）

昨天自己做出来了，然后在网上百度了下发现有更巧妙的方法，这里记录一下。参考博客：[https://blog.csdn.net/renjiewen1995/article/d

Bertha 。/ 2022年05月16日 12:15/ 0 赞/ 154 阅读

相关 LeetCode——最长有效括号（自己想出来的思路）

题目：给定一个只包含 `'('` 和 `')'` 的字符串，找出最长的包含有效括号的子串的长度。示例 1: 输入: "(()" 输出: 2 解

谁践踏了优雅/ 2022年05月16日 10:20/ 0 赞/ 155 阅读

相关 LeetCode 32. Longest Valid Parentheses (最长有效括号)

题目描述：给定一个只包含 `'('` 和 `')'` 的字符串，找出最长的包含有效括号的子串的长度。示例：输入: "(()" 输出: 2 解

╰+哭是因爲堅強的太久メ/ 2022年05月11日 04:04/ 0 赞/ 127 阅读

相关 Leetcode算法Java全解答--32. 最长有效括号

Leetcode算法Java全解答–32. 最长有效括号文章目录 Leetcode算法Java全解答--32. 最长有效括号题目

怼烎@/ 2022年04月13日 14:20/ 0 赞/ 155 阅读