Python 中的最長有效括號

假設我們有一個包含左括號和右括號的字串。我們必須找到最長的有效（格式正確的）括號長度。因此，如果輸入類似於“))(())())”，則結果將為 6，因為有效字串為“(())()”。

為了解決此問題，我們將按照以下步驟進行操作 −

  • 建立一個堆疊並插入 -1，設定 ans := 0

  • 對於 i 在堆疊長度範圍的 0 到 length – 1 之間

    • 如果 s[i] 為左括號，則將 i 插入堆疊

    • 否則

      • 如果堆疊不為空且堆疊頂部不為 -1 且 s[堆疊頂部] 為左括號，則

        • 從堆疊中彈出頂部元素

        • 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

更新於：2020 年 5 月 26 日

1K+ 瀏覽量

啟動你的 職業生涯

完成課程，獲得認證

開始
廣告