JAVA:实现LongestValidParentheses最长有效括号算法（附带源码）

m0_61840987

968人浏览 · 2025-08-20 00:15:00

m0_61840987 · 2025-08-20 00:15:00 发布

JAVA 实现 Longest Valid Parentheses（最长有效括号）算法

一、项目背景详细介绍

括号匹配问题是编程面试与算法题中非常经典的考察点之一。常见的括号问题有：

有效括号验证（Valid Parentheses）：判断给定括号字符串是否为有效表达式，例如 "()[]{}" 是否有效。
生成括号（Generate Parentheses）：给定 n，生成所有可能的有效括号组合。
最长有效括号（Longest Valid Parentheses）：给定括号字符串，返回其中最长的有效括号子串的长度。

其中，Longest Valid Parentheses（最长有效括号） 被认为是较难的问题之一，因为它不仅需要判断括号是否匹配，还需要在所有可能的子串中找到最长的那一个。

例如：

输入："(()" → 输出：2（最长有效子串是 "()"）
输入：")()())" → 输出：4（最长有效子串是 "()()"）
输入："" → 输出：0

这个问题涉及 动态规划、栈、双指针 等多种解法，是学习算法过程中必做的一道题。

二、项目需求详细介绍

功能需求
- 输入：一个仅包含 '(' 和 ')' 的字符串 s。
- 输出：一个整数，表示 s 中最长有效括号子串的长度。
输入要求
- 字符串长度范围：0 <= s.length <= 3 * 10^4。
- 字符串只包含 '(' 和 ')'。
输出要求
- 返回一个非负整数，表示最长有效括号子串的长度。
性能要求
- 时间复杂度要求接近 O(n)。
- 空间复杂度要求尽可能低。
测试需求
- 输入空串。
- 输入全部无效括号串（如 "((((" 或 "))))"）。
- 输入包含多个有效子串（如 ")()())()"）。
- 输入大规模字符串（数万长度）。

三、相关技术详细介绍

为了解决这个问题，我们可以使用多种方法：

1. 栈方法

思路：使用栈存储索引，遇到 '(' 入栈，遇到 ')' 出栈并计算长度。
优点：直观，容易实现。
缺点：需要额外的空间 O(n)。

2. 动态规划方法

状态定义：dp[i] 表示以下标 i 结尾的最长有效括号长度。
状态转移：
- 如果 s[i] == ')' && s[i-1] == '('，那么 dp[i] = dp[i-2] + 2。
- 如果 s[i] == ')' && s[i-1] == ')' && s[i-dp[i-1]-1] == '('，那么
  dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
优点：时间复杂度 O(n)，结果准确。
缺点：需要 O(n) 空间。

3. 双向遍历（贪心方法）

从左向右遍历：统计 '(' 和 ')' 数量，如果两者相等，更新结果；如果 ')' > '('，重置计数。
从右向左遍历：同样的方法，防止遗漏。
优点：时间复杂度 O(n)，空间复杂度 O(1)。
缺点：需要两次遍历。

在本项目中，我们选择 动态规划方法（DP），因为它逻辑清晰，能够保证覆盖所有情况。

四、实现思路详细介绍

初始化
- 如果字符串为空或长度小于 2，直接返回 0。
- 定义数组 dp[n]，其中 dp[i] 表示以下标 i 结尾的最长有效括号长度。
递推公式
- 情况一：s[i] == ')' && s[i-1] == '('
  dp[i] = dp[i-2] + 2
- 情况二：s[i] == ')' && s[i-1] == ')'
  - 如果 s[i - dp[i-1] - 1] == '('，说明形成了新的匹配：
    dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]
结果更新
- 遍历过程中不断更新 maxLen = Math.max(maxLen, dp[i])。
返回结果
- 最终返回 maxLen。

五、完整实现代码

// ==========================================
// 文件：LongestValidParentheses.java
// 功能：使用动态规划实现最长有效括号算法
// ==========================================

public class LongestValidParentheses {

    /**
     * 动态规划解法：最长有效括号
     * @param s 输入字符串
     * @return 最长有效括号长度
     */
    public int longestValidParentheses(String s) {
        int n = s.length();
        if (n < 2) return 0;

        int[] dp = new int[n]; // dp[i] 表示以 i 结尾的最长有效括号
        int maxLen = 0;

        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == ')') {
                // 情况1：形如 "()"
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                }
                // 情况2：形如 "...))"
                else if (i - dp[i - 1] - 1 >= 0 &&
                         s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + 2 +
                            (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                }
                maxLen = Math.max(maxLen, dp[i]);
            }
        }
        return maxLen;
    }

    // 主方法：测试
    public static void main(String[] args) {
        LongestValidParentheses solver = new LongestValidParentheses();

        String s1 = "(()";
        String s2 = ")()())";
        String s3 = "";
        String s4 = "((()))";
        String s5 = "()(()";

        System.out.println("测试用例1: " + solver.longestValidParentheses(s1)); // 2
        System.out.println("测试用例2: " + solver.longestValidParentheses(s2)); // 4
        System.out.println("测试用例3: " + solver.longestValidParentheses(s3)); // 0
        System.out.println("测试用例4: " + solver.longestValidParentheses(s4)); // 6
        System.out.println("测试用例5: " + solver.longestValidParentheses(s5)); // 2
    }
}

六、代码详细解读

longestValidParentheses(String s)
- 输入字符串 s，输出最长有效括号长度。
- 特判：当 s.length() < 2 时直接返回 0。
- 定义数组 dp，长度与 s 相同。
主循环
- 从 i = 1 开始（因为 i=0 不可能构成有效括号）。
- 当 s.charAt(i) == ')' 时，可能构成有效括号：
  - 情况1：前一个是 '('，则 dp[i] = dp[i-2] + 2。
  - 情况2：前一个是 ')'，需要检查 s[i-dp[i-1]-1] 是否是 '('，如果是，则更新。
更新 maxLen
- 每次更新 dp[i] 后，更新 maxLen。
返回结果
- 遍历结束后返回 maxLen。
测试部分
- 验证了多种输入，包括空串、嵌套括号、多个分段的括号串。