最长有效括号【python版】

先来看下题目：

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

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-valid-parentheses
 

---

上面这道题很多人用动态规划来做【不过自己这里太笨了，没做出来】。参考了另一位大佬的做法，他是用了一个mask，用来记录括号是否匹配，将不匹配的地方全部置为1，最后就转化成了求这个mask中连续0【满足匹配】元素的长度。这里我用python进行了实现，先附完整代码：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if s == "":
            return 0
        stack = []
        mask = [0 for _ in range(len(s))]
        left,Len, ans =0,0,0
        for i in range(len(s)):
            if s[i] == '(': # 如果是左括号就加入栈
                   stack.append(i)
            else:
                if stack == []:# 如果栈为空
                    mask[i] = 1
                else: # 如果栈不为空，且为右括号，例如[(()] stack = [0,1,2]
                    stack.pop() # 右括号出栈[((] stack =[0,1]
        while stack != []:
            mask[stack[-1]] = 1 # 另无效的左括号为1
            stack.pop() # stack = [0]  [(]
        for i in range(len(s)):
            if mask[i]:
                Len = 0
                continue
            Len += 1
            ans = max(ans,Len)
        return ans
 
 

步骤：

1.如果s=""，也就是输入为空，直接返回0

2.创造一个与字符串s长度一样的mask列表，并初始化为0，同时stack为栈，用来存储括号

3.for遍历s，然后有两个情况需要判断一下，第一种就是s的第一个元素是左括号"("，第二种就是第一个元素为右括号”）“。

第一种，如果遇到左括号"("，入栈stack.append(i)【这里放入的是下角标】。

如果第一个元素不是左括号【也就是第一个元素是右括号】，那么刚开始的stack没有左括号入栈，也就是刚开始是空，则mask对应的第一个角标位置为1，表示无效的匹配。

如果stack不为空【表示第一次for循环有”(“入栈】且是右括号，匹配成功，那么就执行stack.pop()，将这个右括号")"弹出。【弹出就只剩下左括号继续和后面的匹配】

4.通过上面的for循环匹配过滤多余或者说无效的右括号，还遗留了一个问题，那就是可能会有多余的左括号，因此需要将多余的左括号标记出来，所以我们可以用stack[-1]获得栈最上面的左括号的角标【C++中就是stack.top()】，每标记一次的同时，并将这个多余的也就是栈最上面的左括号弹出。在mask中标记出来并令其为1；【也就是代码中的mask[stack[-1]]】,直到stack为空的时候结束循环，这样我们就得到一个完整mask模板，它清楚的记录了记录了有效括号的下角标。

5.获得mask中连续0最长的长度即可