求最长有效括号

Terence888

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack=[]
        maxL=0
        n=len(s)
        tmp=[0]*n         #标记数组
        cur=0

        for i in range(n):
            if s[i]=='(':
                stack.append(i)
            else:
                if stack:
                    j=stack.pop()
                    tmp[i],tmp[j]=1,1      #匹配成功时标记    
            
        for num in tmp:    #计算连续1出现的最大次数
            if num:
                cur+=1
            else:          #遇到0时中断，进行对比，并重置
                maxL=max(cur,maxL)  
                cur=0
        maxL=max(cur,maxL) #最后一次统计可能未终断，多做一次对比
        
        return maxL

代码如上，为什么要多做一次对比

maxL=max(cur,maxL)

FishC

在最后一行 `maxL = max(cur, maxL)` 中进行一次额外的比较是因为在遍历标记数组 `tmp` 的过程中，当连续的数字 `1` 中断时（遇到 `0` 时），我们才会去更新 `maxL` 并重置 `cur`。但是，如果数组 `tmp` 的最后一个元素是 `1`，那么在 `for` 循环结束时，`cur` 中可能仍会有未更新到 `maxL` 的累计值。因此，需要在循环结束之后再进行一次比较，以确保不会遗漏以最后一个元素结尾的最长连续有效括号子串。

这样可以处理下面这种情况：如果 `tmp` 的末尾有连续的 `1` 且没有被 `0` 打断，为了确保这段连续 `1` 的长度被纳入 `maxL` 的比较，必须在循环结束后再进行一次额外的更新。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。