Pythonで有効な最長の括弧

これを解決するには、次の手順に従います-

• スタックを作成し、-1を挿入し、ans：=0

  を設定します。

• 0からスタックの長さまでの範囲のiの場合– 1

  • s [i]が開き括弧の場合は、iをスタックに挿入します

  • それ以外の場合

    • スタックが空でなく、スタックの最上位が-1でなく、s [stack top]が開き括弧である場合、

      • スタックの最上位要素

      • ans：=ansとiの最大値–スタックトップ

    • それ以外の場合は、iをスタックに挿入します

• ansを返す

例

理解を深めるために、次の実装を見てみましょう-

class Solution(object):
   def longestValidParentheses(self, s):
      stack = [-1]
      ans = 0
      for i in range(len(s)):
         if s[i] == "(":
            stack.append(i)
         else:
            if stack and stack[-1]!=-1 and s[stack[-1]] == "(":
               stack.pop()
               ans = max(ans,i - stack[-1])
            else:
            stack.append(i)
      return ans
ob = Solution()
print(ob.longestValidParentheses("))(())())"))

入力

"))(())())"

出力

6