题解 | 最长的括号子串

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @return int整型
#
class Solution:
    def longestValidParentheses(self , s: str) -> int:
        # write code here
        # 排除特殊情况
        if len(s)<=1:
            return 0
		# 转字符串为列表，便于操作
        list_s = list(s)
		# 状态记录数组，长度和整个字符串长度相同
        dp = [0 for _ in range(len(list_s))]
		# 最核心的思路，记录的不是“（”而是其在原列表中的位置下标
        left_stack = []
		# 循环进入，当左右匹配时，左右两边下标在dp中标为1，无法匹配的字符不用操作
        for i in range(len(list_s)):
            if list_s[i] == "(":
                left_stack.append(i)
            elif list_s[i] == ")":
                if left_stack:
                    cur = left_stack.pop()
                    dp[cur] = 1
                    dp[i] = 1
        Max,counts = 0,0
		# 寻找那些连在一起的1，然后保存最大值，不要忘记假如一个字符串里面所有字符全部匹配那么elif不会进去，所以记得循环完了之后还要Max取值判断一下
        for i in dp:
            if i == 1:
                counts += 1
            elif i == 0:
                Max = max(Max,counts)
                counts = 0
        Max = max(Max,counts)
        return Max
                    

这题没用动态规划，就是比较简单的思路，重点在于确定匹配的状态设为1，而那些连续匹配的对应的1也是相连的，只要找出最长的1就可以确定最大值，技术上使用栈，而栈中保存的不是“（”而是其对应的在原列表中的位置下标，而“）”的下标就是当前循环的i。

时间复杂度为O(N)：两次长度为N的遍历，总时间为2N，数量级依旧为N

空间复杂度为O(N)：开辟空间有两个，dp大小与str一致，left_stack栈大小平均为N/2