最长有效括号

LeetCode 官方题目链接

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

思路拆解

这道题有多种解法，包括动态规划、栈、以及双向遍历（贪心）。这里我们重点介绍动态规划解法。

动态规划

1. 定义状态：dp[i] 表示以下标 i 结尾的最长有效括号子串的长度。
2. 状态转移方程：
   • 显然，有效的子串必须以 ) 结尾，所以如果 s[i] === '('，则 dp[i] = 0。
   • 如果 s[i] === ')'，我们需要看它前面的字符：
     • 情况 1：s[i-1] === '('。这说明构成了 ...() 的形式。
       • dp[i] = dp[i-2] + 2。
     • 情况 2：s[i-1] === ')'。这说明构成了 ...)) 的形式。我们需要判断 s[i-1] 对应的那个左括号的前面一个字符是否是 (。
       • s[i-1] 对应的左括号位置是 i - dp[i-1] - 1。
       • 如果 s[i - dp[i-1] - 1] === '('，则说明我们可以把当前的 ) 和那个 ( 匹配起来。
       • 此时长度为：dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]（最后这一项是之前的有效长度）。
3. 初始条件：
   • dp 数组初始化为 0。
4. 返回值：
   • dp 数组中的最大值。

栈解法（补充）

• 保持栈底元素为“当前已经遍历过的元素中，最后一个没有被匹配的右括号的下标”。
• 遇到 ( 入栈。
• 遇到 ) 出栈。
  • 如果栈为空，说明当前的 ) 没有匹配的左括号，将当前下标入栈（更新“最后一个没有匹配的右括号”）。
  • 如果栈不为空，当前有效长度为 i - stack.top()。

代码实现

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
    const n = s.length;
    const dp = new Array(n).fill(0);
    let maxLen = 0;

    for (let i = 1; i < n; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') {
                // 情况 1: ...()
                dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] === '(') {
                // 情况 2: ...))
                // i - dp[i-1] - 1 是与当前 s[i] 匹配的左括号位置
                dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0);
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
    }

    return maxLen;
};

运行演示

假设 s = ")()())"：

1. i = 0: ) -> dp[0]=0
2. i = 1: ( -> dp[1]=0
3. i = 2: ) -> s[1]='(' -> dp[2] = dp[0] + 2 = 2。 maxLen=2
4. i = 3: ( -> dp[3]=0
5. i = 4: ) -> s[3]='(' -> dp[4] = dp[2] + 2 = 2 + 2 = 4。 maxLen=4
6. i = 5: ) -> s[4]=')'。
   • dp[4]=4。对应左括号位置 5 - 4 - 1 = 0 -> s[0]=')'。
   • 不匹配 (，dp[5]=0。

最终返回 4。

复杂度分析

• 时间复杂度：$O(n)$，遍历一次字符串。
• 空间复杂度：$O(n)$，需要 dp 数组。