32. 最长有效括号 [hard]

https://leetcode-cn.com/problems/longest-valid-parentheses/

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

示例 1:

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

示例 2:

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

通过次数62,506 | 提交次数203,345

Second Try

2020-06-24

虽然看到题解说可以用stack栈的方法来解决，但是想来想去还是不知道怎么搞。仍然需要详细看下题解，才能了解到思路。结果写的时候才发现重点是把"("的index放进去，计算的时候类似于消消乐，计算至今已经消除了多少个元素即可。失败的")"也需要放进去，用来占位置。

就算写的时候知道了思路，但依然写出了一堆bug，还是需要通过测试案例把边界条件都补全了才搞定。不过至少这个版本是最容易理解的版本了。

normal stack version

正常stack版本的写法，在stack能被完全消除的时候需要注意下。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int

        也是一种很巧妙的写法，类似于消消乐，当可以消除的时候，记录中间已经消除了多少个元素。
        当不能消除的时候，把异物放进去进行阻挡。
        wtf: "())" 又错误了; "()()"又错误了，什么鬼。
        如果stack只剩下1了，说明前面都被消除掉了，直接使用i+1即可。
        """
        stack = []
        max_count = count = 0
        for i in range(len(s)):
            if s[i] == ")":
                if len(stack) and s[stack[-1]] == "(":
                     # 如果stack为1，说明前面都被消除掉了，只要记录当前的i+1作为消除长度即可
                    gap = i - stack[-2] if len(stack) >= 2 else i + 1 
                    max_count = max(max_count, gap)
                    stack.pop()  # 得扔掉一个
                else:
                    stack.append(i)  # 放入无效的内容用来阻挡
            else:
                stack.append(i)
        return max_count

prefilled stack version

stack初始状态为[-1]，一下子还是很难想到这个方法的

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int

        也是一种很巧妙的写法，类似于消消乐，当可以消除的时候，记录中间已经消除了多少个元素。
        当不能消除的时候，把异物放进去进行阻挡。
        stack需要提前放一个-1进去垫底，不然无法知道前面是否都被消除了。不垫底也行，直接判断长度即可。
        """
        stack = [-1]  # 放一个垫底，知道已经消除了多少个
        max_count = count = 0
        for i in range(len(s)):
            if s[i] == ")":
                if len(stack) >= 2 and s[stack[-1]] == "(":
                    gap = i - stack[-2]
                    max_count = max(max_count, gap)
                    stack.pop()  # 得扔掉一个
                else:
                    stack.append(i)  # 放入无效的内容用来阻挡
            else:
                stack.append(i)
        return max_count

bug version

在stack能被完全消除的时候，计数方法出现了问题，又是一个bug版本。

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int

        也是一种很巧妙的写法，类似于消消乐，当可以消除的时候，记录中间已经消除了多少个元素。
        当不能消除的时候，把异物放进去进行阻挡。
        wtf: "())" 又错误了; "()()"又错误了，什么鬼: 因为stack只剩下1，无法判断之前被取消了多少个元素
        """
        stack = []
        max_count = count = 0
        for i in range(len(s)):
            if s[i] == ")":
                if len(stack) and s[stack[-1]] == "(":
                    gap = i - stack[-2] if len(stack) >= 2 else i - stack[-1] + 1
                    max_count = max(max_count, gap)
                    stack.pop()  # 得扔掉一个
                else:
                    stack.append(i)  # 放入无效的内容用来阻挡
            else:
                stack.append(i)
        return max_count

First Try

2020-06-24

正序来一波，逆序来一波，结果竟然通过了，但没有经过明确证明还是不太相信

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        mop = {"(": 1, ")": -1}
        max_count = sump = count = 0
        for i in range(len(s)):
            sump += mop[s[i]]
            if sump < 0:
                sump = count = 0
            elif s[i] == ")":
                count += 2
                if sump == 0:
                    max_count = max(max_count, count)
        # print(max_count)
        sump = count = 0
        for i in reversed(s):
            sump += mop[i]
            if sump > 0:
                sump = count = 0
            elif i == "(":
                count += 2
                if sump == 0:
                    max_count = max(max_count, count)
        return max_count

执行用时 :68 ms, 在所有 Python 提交中击败了15.57%的用户
内存消耗 :13.1 MB, 在所有 Python 提交中击败了16.67%的用户

error version

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int

        没有通过这一项测试："()(()"
        """
        max_count = 0
        sump = 0
        count = 0
        mop = {"(": 1, ")": -1}
        for i in range(len(s)):
            sump += mop[s[i]]
            if sump < 0:
                sump = 0
                count = 0
                continue                
            if s[i] == ")":
                count += 2
                max_count = max(max_count, count)
        return max_count
                

32. 最长有效括号 [hard]​

Second Try​

First Try​

32. 最长有效括号 [hard]

Second Try

First Try