LeetCode热题Hot100 - 最长有效括号

一刷~

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

 思路：

用栈保存最近的一个非有效括号子串的位置，当遇到'('时，把当前下标入栈。遇到')'时，出栈，出栈后栈为空，说明当前子串不是有效子串，把当前下标入栈；出栈后栈不为空，说明当前弹出的是与后括号相匹配的左括号的下标，更新最长子串的长度（注意是当前下标减去栈顶下标）。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res = 0
        st = [-1]
        
        for i in range(len(s)):
            if s[i] == '(':
                st.append(i)
            else:
                last = st.pop()
                if len(st) == 0:
                    st.append(i)
                else:
                    res = max(res, i-st[-1])
        return res