静奢之境

LongDz 的数字文墨提案

32. 最长有效括号

3 min

题目

32. 最长有效括号 困难

解法：动态规划

思路

动态规划，定义 dp[i] 表示以位置 i 结尾的最长有效括号子串的长度。

当 s[i] == ’)’ 时，有两种情况：若 s[i-1]==’(‘，则形成 ”()“，dp[i] = dp[i-2] + 2；若 s[i-1]==’)‘，则检查 s[i-dp[i-1]-1] 是否为 ’(‘，若是则可扩展前面的有效串。这种方法能正确计算所有可能的有效括号子串长度，因为每个位置的状态都依赖于前面已计算的状态，通过状态转移覆盖了所有可能的匹配情况。

  • Step 1: 初始化 dp 数组全为 0，ans 记录最大值
  • Step 2: 遍历字符串从索引 1 到 n-1
  • Step 3: 如果当前字符是 ’)’
  • Step 4: 如果前一个字符是 ’(‘，则 dp[i] = (i >= 2 ? dp[i-2] : 0) + 2
  • Step 5: 如果前一个字符是 ’)‘，计算 j = i - dp[i-1] - 1，如果 j >= 0 且 s[j] == ’(‘，则 dp[i] = dp[i-1] + 2 + (j >= 1 ? dp[j-1] : 0)
  • Step 6: 更新 ans = max(ans, dp[i])
  • Step 7: 返回 ans

复杂度

  • 时间复杂度: O(n)O(n)，其中 n 是字符串长度，只需要一次遍历
  • 空间复杂度: O(n)O(n)，用于存储 dp 数组

代码

class Solution {
public:
    int longestValidParentheses(string s) {
        int n = s.size();
        vector<int> dp(n, 0);
        int ans = 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 {
                    int j = i - dp[i - 1] - 1;
                    if (j >= 0 && s[j] == '(') {
                        dp[i] = dp[i - 1] + 2 + (j >= 1 ? dp[j - 1] : 0);
                    }
                }
            }
            ans = max(ans, dp[i]);
        }

        return ans;
    }
};
动态规划 LeetCode