leetcode32 最长有效括号

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

示例 1:

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

示例 2:

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

解题思路：

使用栈结合字符串的遍历来处理，关键点是：

• 怎么处理入栈出栈的条件
• 栈中的元素是什么
• 怎么获取长度

一个巧妙的办法是，栈中每次存进下标，下标相减即可获得长度，同时，入栈的原则是

当前字符不会消去已有括号元素时，进行入栈。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        '''
        使用栈进行处理，遍历字符串长度，每次压入括号下标，通过下标
        相减得到差值。注意入栈的条件：
        1、栈为空
        2、当前遍历字符为左括号
        3、栈顶为右括号
        注意边界条件：字符串s为空
        以及输入匹配括号序列时，最后一次退栈会造成栈空没有栈顶，需要提前垫-1
        这时的栈空条件就变成栈中只有-1一个元素
        '''
        if not s:
            return 0
        result = 0
        stack = [-1,]
        for i in range(len(s)):
            if '(' == s[i] or len(stack) == 1 or ')' == s[stack[-1]]:
                stack.append(i)
            else:
                stack.pop()
                result = max(result, i - stack[-1])
        return result