32. 最长有效括号

[webVueBlog]

32. 最长有效括号

Description

Difficulty: 困难

Related Topics: 栈, 字符串, 动态规划

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

提示：

• 0 <= s.length <= 3 * 10⁴
• s[i] 为 '(' 或 ')'

Solution

Language: JavaScript

/**
 * @param {string} s
 * @return {number}
 */
// 定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。
/**
)()())

push: 一个参照物；左括号

pop：左括号，一个参照物

保持栈不能为空

[-1]
 */
const longestValidParentheses = (s) => {
    let n = s.length
    let res = 0
    let stack = [-1]
    for (let i = 0; i < n; i++) {
        let str = s[i]
        if (str === '(') {
            stack.push(i)
        } else {
            stack.pop()
            if (stack.length) {
                res = Math.max(res, i - stack[stack.length - 1])
            } else {
                stack.push(i)
            }
        }
    }
    return res
};