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

示例 1：

输入：s = “(()” 输出：2

解释：最长有效括号子串是 “()”
示例 2：

输入：s = “)()())” 输出：4

解释：最长有效括号子串是 “()()”
示例 3：

输入：s = “” 输出：0

leetcode题解

思路一：栈

  1. class Solution:
  2.     def longestValidParentheses(self, s: str) -> int:
  3.         ans=0
  4.         stk=[-1] # 为了满足第一个未匹配的右括号放入栈中，初始栈元素为-1
  5.         # 遇到每个"("下标入栈
  6.         # 遇到每个")"我们先弹出栈顶元素表示匹配了当前右括号
  7.         # 栈底元素为最后一个没有匹配的右括号下标，其余都为左括号下标
  8.         for i in range(len(s)):
  9.             if s[i]=='(':
  10.                 stk.append(i)
  11.             else:
  12.                 stk.pop()
  13.                 if not stk:
  14.                     stk.append(i) # 将最后一个没有被匹配的右括号的下标放在栈底
  15.                 else:
  16.                 #如果栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度
  17.                     ans=max(ans,i-stk[-1])
  18.         return ans