Leetcode32-最长有效括号-Python实现

• 题目要求：

• 思路：

  • 括号匹配，最开始想到的应该是栈，因为需要统计长度，所以栈中用来存下标

  • 分为两种情况：

    • 当前字符为“）”时，先弹出栈顶的元素
    • 然后检测栈是否为空，如果为空，把当前字符的下标存入栈中
    • 如果不为空，用当前的字符下标减去栈顶元素的下标，得到当前子串的长度，与当前最大的长度 res 作比较，res 为（res，当前子串的长度）中大的那一个。
    • 当字符为“（”时，直接把当前下标 append 到栈中，因为左括号不能与前面的括号进行匹配
  • 初始化的时候，栈应当添加元素“-1”，因为如果字符串的第一个字符是“）”，需要弹出。
  • 也是因为需要弹出，所以如果弹出后栈为空，要把当前的“）”的下标存到栈中，防止下一位还是“）”
• 核心代码：

# 初始化栈
stack = [-1]
res = 0
for i in range(len(s)):
    if s[i] == ")":
        stack.pop()
        if not stack:
            stack.append(i)
        else:
            res = max(res, i - stack[-1])
    else:
        stack.append(i)
return res         

• 完整代码：

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