61-最大有効かっこ-leetCode 32(python)

タイトル説明

'('および')'のみを含む文字列が与えられ、最も長い有効な括弧を含むサブ列の長さが見出される.

例

例1:
入力:「()」出力:2解釈:最大有効かっこ子列が「()」
例2:
入力:")()()"出力:4解釈:最大有効かっこ子列が"()()"

構想

問題解の一般的な考え方:文字列で一致するカッコペアの下付き記号を見つけ、これらの下付き記号を1つの配列にまとめ、並べ替え、並べ替え後の配列で最も長い数値連続のサブシーケンス長を探します.サブシーケンスの長さは要求され、最も長い括弧を含むサブ列の長さです.

コード

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s:
            return 0
        #         
        res = []
        #    (        
        stack = []
        #     
        for i in range(len(s)):
            #     ),                 (，    )(      res  
            if stack and s[i] == ")":
                res.append(stack.pop())
                res.append(i)
            #     (，               
            if s[i] == "(":
                stack.append(i)
        # res    
        res.sort()
        
        i = 0
        ans = 0
        n = len(res)
        #                  
        while i < n:
            j = i
            while j < n-1 and res[j+1] == res[j] + 1:
                j += 1
            ans = max(ans,j-i+1)
            i = j + 1
        return ans