32. 最长有效括号

力扣题目链接 (opens new window)

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

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

思路

本题和 20. 有效的括号 类似，但难度更高——不仅要判断是否有效，还要找最长的有效子串。

方法一：栈（推荐）

括号匹配，第一反应是用栈。但本题要求的是子串长度，不只是匹配。

核心思路：栈中存放下标，而不是字符本身。

具体做法：

1. 初始化栈，压入 -1 作为"参照物"（表示有效子串的起始位置的前一个位置）
2. 遍历字符串：
   • 遇到 '('，下标入栈
   • 遇到 ')'，栈顶出栈（对应的 '(' 匹配掉）
     • 如果栈空了，说明当前 ')' 无法匹配，将当前下标入栈（作为新的参照物）
     • 如果栈不空，当前下标减去栈顶下标，就是当前有效子串的长度

为什么要在栈底放-1？

因为计算长度时，需要知道有效子串的起始位置。栈底的元素就是"上一个未匹配的 ')' 的位置"，或者初始的-1。

方法二：动态规划

定义 dp[i]：以下标 i 结尾的最长有效括号的长度。

• 如果 s[i] == '('，dp[i] = 0（左括号不可能是有效括号的结尾）
• 如果 s[i] == ')'：
  • 如果 s[i-1] == '('，是 "...()"，dp[i] = dp[i-2] + 2
  • 如果 s[i-1] == ')'，是 "...))"：
    • 找到 i-1 对应的有效括号的起始位置 j = i - dp[i-1] - 1
    • 如果 s[j] == '('，可以匹配，dp[i] = dp[i-1] + 2 + dp[j-1]

最后返回 dp 数组的最大值。

下面用方法一（栈）实现。

模拟过程

以示例 2 为例，s = ")()())"：

下标： 0 1 2 3 4 5
字符： ) ( ) ( ) )

初始化： 栈 = [-1]

i=0, s[0]=')'：

• 栈顶-1出栈，栈空，将0入栈
• 栈 = [0]

i=1, s[1]='('：

• 1入栈
• 栈 = [0, 1]

i=2, s[2]=')'：

• 栈顶1出栈（匹配），栈顶现在是0
• 长度 = 2 - 0 = 2
• 栈 = [0]，maxLen = 2

i=3, s[3]='('：

• 3入栈
• 栈 = [0, 3]

i=4, s[4]=')'：

• 栈顶3出栈（匹配），栈顶现在是0
• 长度 = 4 - 0 = 4
• 栈 = [0]，maxLen = 4

i=5, s[5]=')'：

• 栈顶0出栈，栈空，将5入栈
• 栈 = [5]，maxLen = 4

最终答案：4

解题代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int maxLen = 0;
        stack<int> stk;
        stk.push(-1); // 初始参照物
        
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                stk.push(i); // 左括号下标入栈
            } else {
                stk.pop(); // 右括号，栈顶出栈
                if (stk.empty()) {
                    stk.push(i); // 栈空了，当前右括号无法匹配，入栈作为新参照物
                } else {
                    maxLen = max(maxLen, i - stk.top()); // 计算长度
                }
            }
        }
        
        return maxLen;
    }
};

复杂度分析

• 时间复杂度：O(n)，遍历一遍字符串
• 空间复杂度：O(n)，栈的空间

其他语言

Python3

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        maxLen = 0
        stack = [-1]  # 初始参照物
        
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                stack.pop()
                if not stack:
                    stack.append(i)  # 无法匹配，作为新参照物
                else:
                    maxLen = max(maxLen, i - stack[-1])
        
        return maxLen

Java

class Solution {
    public int longestValidParentheses(String s) {
        int maxLen = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        
        return maxLen;
    }
}

Go

func longestValidParentheses(s string) int {
    maxLen := 0
    stack := []int{-1}
    
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            stack = append(stack, i)
        } else {
            stack = stack[:len(stack)-1]
            if len(stack) == 0 {
                stack = append(stack, i)
            } else {
                maxLen = max(maxLen, i - stack[len(stack)-1])
            }
        }
    }
    
    return maxLen
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

JavaScript

var longestValidParentheses = function(s) {
    let maxLen = 0;
    const stack = [-1];
    
    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.length === 0) {
                stack.push(i);
            } else {
                maxLen = Math.max(maxLen, i - stack[stack.length - 1]);
            }
        }
    }
    
    return maxLen;
};

动态规划解法

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        if (n == 0) return 0;
        
        vector<int> dp(n, 0);
        int maxLen = 0;
        
        for (int i = 1; i < n; i++) {
            if (s[i] == ')') {
                if (s[i-1] == '(') {
                    // 形如 "...()"
                    dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
                } else if (i - dp[i-1] > 0 && s[i - dp[i-1] - 1] == '(') {
                    // 形如 "...)))"
                    dp[i] = dp[i-1] + 2 + (i - dp[i-1] >= 2 ? dp[i - dp[i-1] - 2] : 0);
                }
                maxLen = max(maxLen, dp[i]);
            }
        }
        
        return maxLen;
    }
};

与代码随想录联系

本题结合了栈和动态规划两种思路。

在代码随想录中，栈的专题里讲解了：

• 20. 有效的括号 — 基础的括号匹配
• 84. 柱状图中最大的矩形 — 单调栈的应用

本题的关键：栈中存下标，而不是字符。 这样才能计算长度。

在动态规划专题中，讲解了状态定义和状态转移的方法。本题的 dp 定义比较巧妙："以 i 结尾的最长有效括号"，状态转移需要分情况讨论。

如果录友们对栈还不熟悉，建议先做基础的括号匹配题；如果对动态规划不熟悉，建议先学习 代码随想录动态规划章节。