Algorithm

Appearance

32. 最长有效括号 ​

  • 题号：32
  • 来源：LeetCode
  • 难度：困难
  • 标签：dp 字符串 括号
  • 语言：TypeScript
  • 解法：1 个
  • 作者：lmliheng
  • 最近更新：2026-09-27

TypeScript · O(n) 时间 · O(n) 空间 · 更新于 2026-09-27

dp 记录以 i 结尾的最长有效括号长度

typescript
/**
 * @difficulty hard
 * @tags dp,字符串,括号
 * @time O(n)
 * @space O(n)
 * @note dp 记录以 i 结尾的最长有效括号长度
 * @32. 最长有效括号
 */


function longestValidParentheses(s: string) {
    let max = 0;
    // dp[i]：s[0]...s[i]的字符串 的最长有效子串长度
    const dp = new Array(s.length).fill(0);
    for (let i = 1; i < s.length; i++) {
        if (s[i] === ')') {
            if (s[i - 1] === '(') {

                if (i >= 2) {
                    dp[i] = dp[i - 2] + 2
                } else {
                    dp[i] = 2
                }

                // s[i]和s[i-1]为)，看s[i-dp[i-1]]是否是
            } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] === '(') {

                if ((i - dp[i - 1]) >= 2) {
                    dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2
                } else {
                    dp[i] = dp[i - 1] + 2
                }

            }
            max = Math.max(max, dp[i]);
        }
    }
    // console.log(dp)
    return max;
};

源码：ts/leetcode/32. 最长有效括号.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm