求最长有效括号

Terence888

1. class Solution:
   
2.     def longestValidParentheses(self, s: str) -> int:
   
3.         stack=[]
   
4.         maxL=0
   
5.         n=len(s)
   
6.         tmp=[0]*n         #标记数组
   
7.         cur=0
   
8. 
   
9.         for i in range(n):
   
10.             if s[i]=='(':
    
11.                 stack.append(i)
    
12.             else:
    
13.                 if stack:
    
14.                     j=stack.pop()
    
15.                     tmp[i],tmp[j]=1,1      #匹配成功时标记   
    
16.             
    
17.         for num in tmp:    #计算连续1出现的最大次数
    
18.             if num:
    
19.                 cur+=1
    
20.             else:          #遇到0时中断，进行对比，并重置
    
21.                 maxL=max(cur,maxL)  
    
22.                 cur=0
    
23.         maxL=max(cur,maxL) #最后一次统计可能未终断，多做一次对比
    
24.         
    
25.         return maxL
    
26. 
    

复制代码

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

1. 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 小助理，如未能正确解答您的问题，请继续追问。