32 最长有效括号

一、题目

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

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

二、题解

方法一：动态规划

思路：动态规划。

1. 核心思路

定义：

dp[i]：以字符 s[i] 结尾的最长有效括号子串长度

由于一个有效括号子串一定以右括号 ')' 结尾，因此：

  • 当 s[i] == '(' 时，dp[i] = 0；
  • 当 s[i] == ')' 时，才有可能形成有效括号。

当 s[i] == ')' 时，根据前一个字符的不同，可以分为两种情况。

情况一：前一个字符是 '('

当前两个字符组成：

()

此时：

dp[i] = dp[i - 2] + 2

其中：

  • 2 表示当前匹配成功的一对括号；
  • dp[i - 2] 表示这对括号前面连续的有效括号长度。

例如：

s = "()()"
         ↑

处理最后一个右括号时，当前的 "()" 长度为 2，前面还有一个 "()"，因此总长度为 4。

情况二：前一个字符是 ')'

例如：

s = "(())"
        ↑

此时不能直接让 s[i - 1] 和 s[i] 匹配，因为它们都是右括号。

需要先跳过以 i - 1 结尾的有效括号：

left = i - dp[i - 1] - 1

left 就是可能与当前右括号 s[i] 匹配的位置。

如果：

left >= 0，并且 s[left] == '('

说明匹配成功。

此时：

dp[i] = dp[i - 1] + 2 + dp[left - 1]

其中：

  • dp[i - 1]：当前右括号前面的有效括号长度；
  • 2：新匹配的一对左右括号；
  • dp[left - 1]：新匹配的左括号前面连续的有效括号长度。

2. 具体步骤

  1. 创建长度为 s.length() 的数组 dp。
  2. 定义 answer，记录最长有效括号的长度。
  3. 从下标 1 开始遍历字符串。
  4. 如果当前字符是 '('，不进行处理，因为有效括号不能以左括号结尾。
  5. 如果当前字符是 ')'：
    • 前一个字符是 '('，说明形成了直接匹配的 "()"；
    • 前一个字符是 ')'，跳过前面的有效括号，寻找可以匹配的左括号。
  6. 每次计算出 dp[i] 后，更新最大值。
  7. 遍历结束后返回 answer。

3. 关键逻辑

if (s.charAt(i - 1) == '(') {
    // 情况一：当前两个字符组成 "()"
    dp[i] = 2;

    // 加上前面连续的有效括号
    if (i >= 2) {
        dp[i] += dp[i - 2];
    }
} else {
    // 情况二：前一个字符是 ')'
    int left = i - dp[i - 1] - 1;

    if (left >= 0 && s.charAt(left) == '(') {
        dp[i] = dp[i - 1] + 2;

        // 连接 left 前面的有效括号
        if (left >= 1) {
            dp[i] += dp[left - 1];
        }
    }
}

解释：

  • 如果 s[i - 1] == '('，说明 s[i - 1] 和 s[i] 可以直接组成 "()"；
  • 如果 s[i - 1] == ')'，说明前面可能已经存在一段有效括号；
  • 使用 i - dp[i - 1] - 1 跳过这段有效括号，找到可能匹配的左括号；
  • 匹配成功后，还要加上更前面连续的有效括号长度。

4. 代码

class Solution {
    public int longestValidParentheses(String s) {
        // 1. 处理特殊情况
        if (s == null || s.length() < 2) {
            return 0;
        }

        // 2. 定义动态规划数组
        // dp[i] 表示以 s[i] 结尾的最长有效括号长度
        int[] dp = new int[s.length()];

        // 记录最终答案
        int answer = 0;

        // 3. 核心逻辑
        // 有效括号至少包含两个字符，因此从下标 1 开始
        for (int i = 1; i < s.length(); i++) {
            // 有效括号一定以右括号结尾
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    /*
                     * 情况一：
                     *
                     * 当前两个字符组成 "()"
                     *
                     * 例如：
                     * s = "()()"
                     *        ^^
                     */
                    dp[i] = 2;

                    // 加上这对括号前面连续的有效括号长度
                    if (i >= 2) {
                        dp[i] += dp[i - 2];
                    }
                } else {
                    /*
                     * 情况二：
                     *
                     * 前一个字符也是 ')'
                     *
                     * 跳过以 i - 1 结尾的有效括号，
                     * 查找能够与当前右括号匹配的左括号。
                     */
                    int left = i - dp[i - 1] - 1;

                    // left 没有越界，并且该位置是左括号
                    if (left >= 0 && s.charAt(left) == '(') {
                        // 前面的有效括号 + 当前新匹配的一对括号
                        dp[i] = dp[i - 1] + 2;

                        // 再连接 left 前面连续的有效括号
                        if (left >= 1) {
                            dp[i] += dp[left - 1];
                        }
                    }
                }

                // 更新最长有效括号长度
                answer = Math.max(answer, dp[i]);
            }
        }

        // 4. 返回结果
        return answer;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：只需要遍历一次字符串，每个字符只处理一次。

空间复杂度：O(n)O(n)

说明：使用了长度为 n 的动态规划数组 dp。

方法二：栈

思路：栈。

1. 核心思路

栈中不存放括号字符，而是存放括号字符的下标。

首先向栈中放入一个哨兵下标：

-1

这个下标表示当前有效括号子串开始位置的前一个位置。

遍历字符串时：

  • 遇到 '('，将它的下标放入栈中；
  • 遇到 ')'，弹出栈顶元素，尝试匹配一个左括号。

弹出后分为两种情况：

情况一：栈为空

说明当前右括号没有可以匹配的左括号。

当前右括号会破坏括号的连续性，因此把当前下标放入栈中，作为新的边界。

情况二：栈不为空

说明当前右括号成功匹配了一个左括号。

此时最长有效括号长度为：

当前下标 - 栈顶下标

也就是：

i - stack.peek()

栈顶下标表示当前有效括号子串左边界的前一个位置。

2. 具体步骤

  1. 创建一个栈，用来存放括号的下标。
  2. 先向栈中放入哨兵下标 -1。
  3. 从左向右遍历字符串。
  4. 如果当前字符是 '('，将当前下标入栈。
  5. 如果当前字符是 ')'：
    • 先弹出栈顶；
    • 如果栈为空，将当前下标作为新的无效边界入栈；
    • 如果栈不为空，使用 i - stack.peek() 计算当前有效括号长度。
  6. 更新最大值。
  7. 返回最大长度。

3. 关键逻辑

if (s.charAt(i) == '(') {
    // 左括号下标入栈
    stack.push(i);
} else {
    // 当前右括号尝试匹配一个左括号
    stack.pop();

    if (stack.isEmpty()) {
        // 没有可以匹配的左括号，更新边界
        stack.push(i);
    } else {
        // 计算以当前右括号结尾的有效括号长度
        answer = Math.max(answer, i - stack.peek());
    }
}

解释：

  • 左括号入栈，等待后面的右括号进行匹配；
  • 遇到右括号时，弹出一个下标，表示完成一次匹配；
  • 如果弹出后栈为空，说明当前右括号没有成功匹配；
  • 如果栈不为空，栈顶就是当前有效括号左边界的前一个位置；
  • 因此使用 i - stack.peek() 可以得到当前有效括号的长度。

4. 为什么需要哨兵 -1

假设：

s = "()"

处理过程如下：

初始栈：[-1]

i = 0，字符为 '('
下标 0 入栈
栈：[0, -1]

i = 1，字符为 ')'
弹出下标 0
栈：[-1]

当前有效括号长度：
1 - (-1) = 2

如果没有哨兵 -1，匹配完成后栈会变成空栈，也就无法计算从字符串开头开始的有效括号长度。

5. 代码

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int longestValidParentheses(String s) {
        // 1. 处理特殊情况
        if (s == null || s.length() < 2) {
            return 0;
        }

        // 2. 创建栈，用来存放括号的下标
        Deque<Integer> stack = new ArrayDeque<>();

        /*
         * 放入哨兵下标 -1。
         *
         * 它表示当前有效括号子串左边界的前一个位置，
         * 用于计算从字符串开头开始的有效括号长度。
         */
        stack.push(-1);

        // 3. 定义结果变量
        int answer = 0;

        // 4. 核心逻辑
        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 {
                    /*
                     * 当前右括号匹配成功。
                     *
                     * 栈顶是当前有效括号子串
                     * 左边界的前一个位置。
                     */
                    int currentLength = i - stack.peek();

                    // 更新最长有效括号长度
                    answer = Math.max(answer, currentLength);
                }
            }
        }

        // 5. 返回结果
        return answer;
    }
}

6. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个字符的下标最多入栈一次、出栈一次。

空间复杂度：O(n)O(n)

说明：最坏情况下，字符串全部由左括号组成，所有下标都会进入栈中。

方法三：两次遍历

思路：双向遍历、计数器。

1. 核心思路

分别使用两个变量记录左右括号的数量：

left：当前区间内左括号的数量
right：当前区间内右括号的数量

先从左向右遍历：

  • 遇到 '('，left++；
  • 遇到 ')'，right++；
  • 当 left == right 时，说明当前区间内左右括号数量相等，可以更新答案；
  • 当 right > left 时，说明右括号过多，当前区间不可能成为有效括号，需要将两个计数器清零。

但是只进行一次从左向右遍历还不够。

例如：

s = "(()"

从左向右遍历结束时：

left = 2
right = 1

此时左括号数量始终多于右括号数量，不会触发清零，但字符串中实际存在长度为 2 的有效括号 "()"。

因此还需要从右向左再遍历一次：

  • 当 left == right 时，更新答案；
  • 当 left > right 时，说明左括号过多，将两个计数器清零。

两次遍历结合起来，就可以同时处理：

  • 右括号过多；
  • 左括号过多。

2. 具体步骤

  1. 定义 left、right 和 answer。
  2. 从左向右遍历字符串：
    • 统计左右括号数量；
    • 当 left == right 时更新答案；
    • 当 right > left 时清空计数器。
  3. 将 left 和 right 重新设置为 0。
  4. 从右向左遍历字符串：
    • 统计左右括号数量；
    • 当 left == right 时更新答案；
    • 当 left > right 时清空计数器。
  5. 返回最终答案。

3. 关键逻辑

从左向右遍历：

if (left == right) {
    // 当前区间左右括号数量相等
    answer = Math.max(answer, left + right);
} else if (right > left) {
    // 右括号数量过多，当前区间失效
    left = 0;
    right = 0;
}

从右向左遍历：

if (left == right) {
    // 当前区间左右括号数量相等
    answer = Math.max(answer, left + right);
} else if (left > right) {
    // 左括号数量过多，当前区间失效
    left = 0;
    right = 0;
}

解释：

  • 从左向右遍历时，右括号数量一旦超过左括号数量，说明出现了无法匹配的右括号；
  • 从右向左遍历时，左括号数量一旦超过右括号数量，说明出现了无法匹配的左括号；
  • 当左右括号数量相等时，当前统计区间是有效括号区间；
  • 使用两次方向相反的遍历，可以处理左右两种括号过多的情况。

4. 为什么需要遍历两次

只从左向右遍历可以处理：

")()())"

因为当右括号数量超过左括号数量时，可以立刻发现当前区间无效。

但它不能正确处理：

"(()"

遍历过程为：

字符 '('：left = 1，right = 0
字符 '('：left = 2，right = 0
字符 ')'：left = 2，right = 1

整个过程中，right 从未大于 left，所以不会清零，也无法统计最后的 "()"。

从右向左重新遍历：

字符 ')'：left = 0，right = 1
字符 '('：left = 1，right = 1

此时左右括号数量相等，可以得到长度：

1 + 1 = 2

因此必须进行两次遍历。

5. 代码

class Solution {
    public int longestValidParentheses(String s) {
        // 1. 处理特殊情况
        if (s == null || s.length() < 2) {
            return 0;
        }

        // 2. 定义左右括号计数器和答案
        int left = 0;
        int right = 0;
        int answer = 0;

        // 3. 第一次：从左向右遍历
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }

            if (left == right) {
                /*
                 * 左右括号数量相等，
                 * 当前区间是有效括号区间。
                 */
                answer = Math.max(answer, left + right);
            } else if (right > left) {
                /*
                 * 右括号数量超过左括号数量，
                 * 当前右括号无法匹配。
                 *
                 * 当前区间已经失效，需要重新统计。
                 */
                left = 0;
                right = 0;
            }
        }

        // 4. 重置计数器
        left = 0;
        right = 0;

        // 5. 第二次：从右向左遍历
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }

            if (left == right) {
                /*
                 * 左右括号数量相等，
                 * 当前区间是有效括号区间。
                 */
                answer = Math.max(answer, left + right);
            } else if (left > right) {
                /*
                 * 从右向左遍历时，
                 * 左括号数量超过右括号数量，
                 * 当前左括号无法匹配。
                 *
                 * 当前区间已经失效，需要重新统计。
                 */
                left = 0;
                right = 0;
            }
        }

        // 6. 返回结果
        return answer;
    }
}

6. 复杂度分析

时间复杂度：O(n)O(n)

说明：分别从左向右和从右向左遍历一次字符串，总共处理 2n 个字符，因此时间复杂度仍然是 O(n)O(n)。

空间复杂度：O(1)O(1)

说明：只使用了固定数量的变量，没有使用与字符串长度相关的额外空间。

三、三种方法对比

方法时间复杂度空间复杂度特点
动态规划O(n)O(n)O(n)O(n)状态转移较复杂，可以记录每个位置的最优结果
栈O(n)O(n)O(n)O(n)思路比较直观，使用下标计算有效括号长度
两次遍历O(n)O(n)O(1)O(1)空间复杂度最优，但需要理解为什么要双向遍历

推荐掌握顺序

  1. 栈：最容易理解，能够清楚地模拟括号匹配过程；
  2. 动态规划：适合练习状态定义和状态转移；
  3. 两次遍历：空间复杂度最优，适合作为进阶优化方法。

评论