每日leetcode--最长有效括号

问题描述

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度

题目链接：. - 力扣（LeetCode）

解决方案

使用栈

我们可以使用栈来解决这个问题。具体步骤如下：

1. 初始化一个空栈和一个变量begin，用于记录当前有效子串的起始位置。
2. 初始化变量ans和count，其中ans用于记录最长有效括号子串的长度，count用于记录当前有效括号子串的长度。
3. 遍历字符串s，对于每个字符char和其对应的索引ind：
   • 如果char是'('，将[char, ind]入栈。
   • 如果char是')'，检查栈是否为空：
     • 如果栈不为空，说明当前字符可以与前面的'('匹配，因此从栈顶弹出一个'('，并将count增加2。
     • 如果栈为空，表示当前字符没有与之匹配的'('，需要更新begin的值，并将ans更新为当前的最大值（即max(ans, count)），同时将count重置为0。
4. 遍历完字符串s后，如果栈不为空，说明还有一些'('没有被匹配。此时，我们需要计算栈中剩余'('的位置之间的距离，即max([stack[i+1][1]-stack[i][1]-1 for i in range(0, len(stack)-1)] or [0])，并与之前的ans取最大值。
5. 最后，我们还需要将ans与count取最大值，以处理s以'('结尾的情况。返回最终的结果。

python代码实现

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack=[]
        begin = 0
        ans=0
        count=0
        for ind, char in enumerate(s):
            if char=='(':
                stack.append([char, ind])
            else:
                if stack:
                    stack.pop()
                    count+=2
                else:
                    # stack=空
                    begin=ind+1
                    ans=max(ans, count)
                    count=0

        if stack:
            # 注意要先max([stack[i+1][1]-stack[i][1]-1 for i in range(0, len(stack)-1)] or [0])后stack.pop(), 不然pop会干扰max
            return max(max([stack[i+1][1]-stack[i][1]-1 for i in range(0, len(stack)-1)] or [0]),stack[0][1]-begin, len(s)-1-stack.pop()[1], ans)
        else:
            return max(ans, count)

复杂度分析

• 时间复杂度：O(n)，其中n是字符串s的长度。我们只需一次遍历字符串s来计算最长有效括号子串的长度。
• 空间复杂度：O(n)，其中n是字符串s的长度。在最坏的情况下，栈的大小将达到n。

总结

本博客介绍了如何使用栈来解决最长有效括号子串的问题。通过遍历字符串s并使用栈来跟踪已经匹配的括号，我们可以计算出最长有效括号子串的长度，并在遍历结束后返回结果。

希望本篇博客能够帮助你理解并解决最长有效括号字符串的问题。如果你有任何疑问或建议，请随时提出。谢谢阅读！

详细题解：. - 力扣（LeetCode）