最长有效括号——DP与栈两种方法的状态定义差异

老张2026/4/30大约 6 分钟

最长有效括号——DP与栈两种方法的状态定义差异

适读人群：Java后端工程师、括号类DP学习者 | 阅读时长：约20分钟 | 难度：Hard

开篇故事

括号类题目是面试里的常客。最长有效括号这道Hard题，我见过很多人用栈做，思路清晰，代码直觉性强。但如果面试官说"用DP做"，很多人就犯难了。

这两种解法的核心差异在于"状态定义"。栈的思路是记录"未配对括号的位置"，通过位置差算长度。DP的思路是"以每个字符结尾的最长有效括号子串长度"。

两者的推理过程截然不同，但最终结果相同。对比着学，既能掌握两种技术，又能加深对"同一问题的不同建模方式"的理解。

一、题目解析

题号：LeetCode 32. Longest Valid Parentheses

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

示例：

输入：s = "(()"，输出：2（"()"）
输入：s = ")()())"，输出：4（"()()"）
输入：s = ""，输出：0

二、解法一：DP方法

2.1 状态定义

定义 dp[i] = 以 s[i] 结尾的最长有效括号子串的长度

注意：s[i] 为 '(' 时，dp[i] = 0（因为有效括号必须以 ')' 结尾，无法以 '(' 结尾）。

所以只需要处理 s[i] = ')' 的情况。

2.2 状态转移方程

当 s[i] = ')' 时，有两种情况：

情况一：s[i-1] = '('（相邻匹配）

s[i-1] 和 s[i] 直接配对。把这对括号加上 i-2 位置结尾的有效括号：

dp[i] = dp[i-2] + 2   （如果i >= 2，否则dp[i] = 2）

情况二：s[i-1] = ')'（前面也是右括号）

此时 s[i-1] 是之前某段有效括号的末尾。以 s[i-1] 结尾的有效括号段长度为 dp[i-1]，往左跳过这段，到达位置 j = i - dp[i-1] - 1。

如果 j >= 0 且 s[j] = '('，则 s[j] 和 s[i] 配对！

dp[i] = dp[i-1] + dp[j-1] + 2   （其中j = i - dp[i-1] - 1，如果j >= 0且s[j]='('）

含义：以 s[i] 结尾的有效括号 = 以 s[i-1] 结尾的那段 + 当前配对的2 + j 之前的有效段

2.3 DP状态转移示意

s = ")()())"
    0 1 2 3 4 5

dp[0]=0  (s[0]=')'，前面没有'('，dp=0)
dp[1]=2  (s[0]='(' 和 s[1]=')' 配对，dp=dp[-1]+2=2)
dp[2]=0  (s[2]='('，无效)
dp[3]=2  (s[2]='('，s[3]=')'，相邻配对，dp=dp[1]+2=4?)
     实际：j=1, dp[3]=dp[2]+2+dp[0]=0+2+2=4 ...(手动验证)

实际dp数组：
s:  )  (  )  (  )  )
dp: 0  0  2  0  4  0
答案：max=4 ✓

public class LongestValidParentheses {
    
    /**
     * 32. 最长有效括号 - DP
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public int longestValidParenthesesDP(String s) {
        int n = s.length();
        if (n == 0) return 0;
        
        int[] dp = new int[n];
        int maxLen = 0;
        
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    // 情况一：相邻匹配
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (dp[i - 1] > 0) {
                    // 情况二：前面是），跳过dp[i-1]长度的有效段，找匹配的（
                    int j = i - dp[i - 1] - 1;
                    if (j >= 0 && s.charAt(j) == '(') {
                        dp[i] = dp[i - 1] + 2;
                        if (j - 1 >= 0) dp[i] += dp[j - 1];  // 加上j左边的有效段
                    }
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        
        return maxLen;
    }
}

Mermaid状态转移图：

三、解法二：栈方法

3.1 栈的核心思路

栈里存放"未被匹配的括号的下标"。

遇到 '('：直接压栈
遇到 ')'：如果栈不为空且栈顶是 '(' 的下标，弹出匹配；否则把当前 ')' 压栈（作为分隔符）

有效括号的长度 = 当前位置 - 栈顶位置（栈顶是最近一个未匹配的括号）

初始化：栈中放入 -1 作为哨兵，代表起始边界。

/**
 * 32. 最长有效括号 - 栈
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */
public int longestValidParenthesesStack(String s) {
    int maxLen = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    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 {
                // 计算以当前i结尾的有效括号长度
                maxLen = Math.max(maxLen, i - stack.peek());
            }
        }
    }
    
    return maxLen;
}

栈方法示意（s = ")()())"）：

初始：stack = [-1]

i=0, s[0]=')': pop(-1), 栈空，push(0)，stack=[-1, 0]... 
（重新理解：初始只有-1，pop后栈空，push 0）

实际演示：
初始: stack=[-1]
i=0, ')': pop→-1，栈空，push 0，stack=[0]
i=1, '(': push 1，stack=[0,1]
i=2, ')': pop→1，stack=[0]，len=2-0=2，maxLen=2
i=3, '(': push 3，stack=[0,3]
i=4, ')': pop→3，stack=[0]，len=4-0=4，maxLen=4
i=5, ')': pop→0，stack=[]，push 5，stack=[5]
答案：4 ✓

四、解法三：双向扫描（O(1)空间）

/**
 * 32. 最长有效括号 - 双向扫描（O(1)空间）
 */
public int longestValidParenthesesTwoPass(String s) {
    int left = 0, right = 0, maxLen = 0;
    
    // 从左向右扫描
    for (char c : s.toCharArray()) {
        if (c == '(') left++;
        else right++;
        if (left == right) maxLen = Math.max(maxLen, 2 * right);
        else if (right > left) left = right = 0;  // 右括号多了，重置
    }
    
    left = right = 0;
    // 从右向左扫描（处理左括号多的情况）
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == '(') left++;
        else right++;
        if (left == right) maxLen = Math.max(maxLen, 2 * left);
        else if (left > right) left = right = 0;
    }
    
    return maxLen;
}