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+ 浏览量

启动你的 职业生涯

完成课程，获得认证

开始
广告