Hard

题目描述

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

示例 1：

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""
输出：0

提示：

  • 0 <= s.length <= 3 * 10^4
  • s[i] 为 '(' 或 ')'

解题思路

这道题有多种解法，我们分析几种常见的方法：

方法一：栈（推荐）

使用栈来追踪括号的匹配情况。关键思路是：

  • 栈中存储字符的索引，初始时压入 -1 作为基准
  • 遇到 ‘(’ 压入当前索引
  • 遇到 ‘)’ 先弹出栈顶，如果栈为空说明当前 ‘)’ 无法匹配，将其索引压入栈作为新的基准；否则当前索引减去栈顶索引就是当前有效括号串的长度

方法二：动态规划

定义 dp[i] 表示以字符 s[i] 结尾的最长有效括号长度：

  • 如果 s[i] = '('，则 dp[i] = 0
  • 如果 s[i] = ')'，需要考虑两种情况：
    • s[i-1] = '('：dp[i] = dp[i-2] + 2
    • s[i-1] = ')' 且 dp[i-1] > 0：需要检查与 s[i] 匹配的 ‘(’ 的位置

方法三：双向扫描

分别从左到右和从右到左扫描，统计左右括号数量，当相等时更新最大长度。

栈方法思路清晰，代码简洁，是最推荐的解法。

代码实现

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int maxLen = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s[i] == '(') {
                st.push(i);
            } else {
                st.pop();
                if (st.empty()) {
                    st.push(i);
                } else {
                    maxLen = max(maxLen, i - st.top());
                }
            }
        }
        
        return maxLen;
    }
};

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stack = [-1]
        max_len = 0
        
        for i, char in enumerate(s):
            if char == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)
                else:
                    max_len = max(max_len, i - stack[-1])
        
        return max_len

public class Solution {
    public int LongestValidParentheses(string s) {
        Stack<int> stack = new Stack<int>();
        stack.Push(-1);
        int maxLen = 0;
        
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') {
                stack.Push(i);
            } else {
                stack.Pop();
                if (stack.Count == 0) {
                    stack.Push(i);
                } else {
                    maxLen = Math.Max(maxLen, i - stack.Peek());
                }
            }
        }
        
        return maxLen;
    }
}

var longestValidParentheses = function(s) {
    const stack = [-1];
    let maxLen = 0;
    
    for (let i = 0; i < s.length; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型栈方法动态规划双向扫描
时间复杂度O(n)O(n)O(n)
空间复杂度O(n)O(n)O(1)

其中 n 为字符串长度。栈方法在最坏情况下需要存储所有字符的索引，动态规划需要额外的 dp 数组，双向扫描的空间复杂度最优。

相关题目