32. 最长有效括号

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

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

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

示例 3：
输入：s = ""
输出：0

提示：
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-valid-parentheses

javascript

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
  const stack = [-1]
  let max = 0
  for (let i = 0; i < s.length; i++) {
    const ele = s[i]
    if(ele === '('){
      stack.push(i)
    }else {
      stack.pop()
      if(stack.length > 0){
        max = Math.max(max, i - stack[stack.length - 1])
      }else {
        stack.push(i)
      }
    }
  }
  return max
}

var longestValidParentheses = function(s) {
  if(s.length === 0) return 0
  const dp = Array.from({ length: s.length }, () => 0)
  let max = 0
  for (let i = 1; i < s.length; i++) {
    if(s[i] === ')'){
      if(s[i - 1] === '('){
        dp[i] = (dp[i - 2] || 0) + 2
      }else if(s[i - dp[i - 1] - 1] === '(') {
        dp[i] = (dp[i - dp[i - 1] - 2] || 0) + dp[i - 1] + 2
      }
      max = Math.max(dp[i], max)
    }
  }
  return max
}


console.log(longestValidParentheses(")()()") === 4)
console.log(longestValidParentheses("()") === 2)
console.log(longestValidParentheses("()()") === 4)
console.log(longestValidParentheses("((())") === 4)
console.log(longestValidParentheses("(()") === 2)
console.log(longestValidParentheses("((") === 0)
console.log(longestValidParentheses(")()())") === 4)
console.log(longestValidParentheses(")()))") === 2)
console.log(longestValidParentheses("))))") === 0)
console.log(longestValidParentheses("()))))") === 2)
console.log(longestValidParentheses("") === 0)

32. 最长有效括号 #

32. 最长有效括号