【面试题】最长有效括号

最长有效括号

仅学习

一、问题描述

二、算法步骤

这个问题可以通过使用栈来解决。栈用于跟踪最近遇到的未匹配的左括号的索引。

• 初始化一个栈，用于存储索引。
• 设置一个变量 maxLen 来存储最长有效括号子串的长度。
• 遍历字符串 s 中的每个字符：

如果字符是 ‘(’，则将其索引压入栈中。

如果字符是 ‘)’：

如果栈不为空且栈顶元素对应的字符是 ‘(’，则弹出栈顶元素，并计算当前索引与栈顶元素索引之间的长度，更新 maxLen。

如果栈为空，则将当前索引压入栈中，表示这是一个未匹配的右括号。

• 遍历结束后，还需要检查栈中剩余的索引，因为它们可能是以左括号开始的有效括号子串的开始位置。
• 对于栈中的每个索引 i，计算从索引 i 到字符串末尾的长度，更新 maxLen。

三、python代码

def longestValidParentheses(s):
    stack = [-1]  # 初始化栈，包含一个哨兵元素
    maxLen = 0
    for i, char in enumerate(s):
        if char == '(':
            stack.append(i)  # 压入索引
        else:
            stack.pop()  # 弹出栈顶元素
            if not stack:
                stack.append(i)  # 未匹配的右括号，压入索引
            else:
                # 计算当前有效括号子串的长度，并更新 maxLen
                maxLen = max(maxLen, i - stack[-1])
    return maxLen

四、算法复杂度

• 算法的时间复杂度是 O(n)，其中 n 是字符串的长度，因为每个字符只被遍历一次。
• 空间复杂度是 O(n)，最坏情况下栈可能包含所有字符的索引。