Python 中最长的有效括号

pythonserver side programmingprogramming更新于 2026/1/15 5:00:17

假设我们有一个字符串，带有左括号和右括号。我们必须找到有效(格式正确)括号的最长长度。因此，如果输入类似于"))(())())"，则结果将为 6，因为有效字符串是"(())()"。

要解决这个问题，我们将遵循以下步骤 −

创建一个堆栈，并插入 -1。，设置 ans := 0
for i in range 0 to length of stack – 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("))(())())"))