Python中最长的有效括号

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

为了解决这个问题，我们将遵循以下步骤-

• 进行堆叠，然后插入-1。，设置ans：= 0

• 对于i，范围为0到堆栈长度– 1

• 如果堆栈不为空并且堆栈顶部不为-1并且s [stack top]是开括号，则

• 否则将我插入堆栈

• 堆栈中的顶部元素

• ans：= ans和i的最大值–堆栈顶部

• 如果s [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