32. 最长有效括号

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

示例 1:

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

示例 2:

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

思路--栈

我们首先将−1 放入栈顶。
对于遇到的每个 \text{‘(’}‘(’ ，我们将它的下标放入栈中。
对于遇到的每个 \text{‘)’}‘)’ ，我们弹出栈顶的元素并将当前元素的下标与弹出元素下标作差，得出当前有效括号字符串的长度。通过这种方法，我们继续计算有效子字符串的长度，并最终返回最长有效子字符串的长度。

动画演示过程参考链接：https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode/

python3解法

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        # if not s: return 0
        stack = []
        stack.append(-1)
        largestlength = 0
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                stack.pop()
                if len(stack) == 0:
                    stack.push(i)
                else:
                    largestlength = max(largestlength, i - stack[-1])
        return largestlength

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。