题目描述

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

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

算法思路

分析题目，很容易可以知道一点，给定字符串一定是由有效括号字符串和无效字符拼接起来的。

反过来看，给定字符串就是被许多无效字符隔开的有效括号串，我们要求的就是被分割的字符串中的最长的那个。

有了这个思路，但是一直卡着没办法实现， 评论区这位大佬给了我思路，嘿。

我们如何知道哪些左括号是多余的？遍历一遍后剩下的就是多余的，只要入栈的是左括号的ID，那么最后我们就知道哪些是多余左括号了。

算法

class Solution: def longestValidParentheses(self, s: str) -> int: # ls：栈，用来进行括号匹配 # lst：列表，用来保存多余右括号的位置 ls,lst=[],[] # 遍历一遍s for i,j in enumerate(s): # 将所有左括号的ID入栈 if j=='(': ls.append(i) else: # 对右括号，如果此时ls为空，那么这个右括号就是多余的，放入lst # 否则就是有效的右括号，与栈中左括号ID抵消 if ls: ls.pop() else: lst.append(i) # 将所有的阻隔合并排序并添加上左右边界 c=[-1]+sorted(ls+lst)+[len(s)] MAX=0 # 最后遍历阻隔数组，计算差值既是所求值 for i in range(len(c)-1): MAX=max(MAX,c[i+1]-c[i]-1) return MAX

执行用时：52 ms, 在所有 Python3 提交中击败了87.15%的用户 内存消耗：14.4 MB, 在所有 Python3 提交中击败了11.11%的用户