最长有效括号.md

最长有效括号

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

示例 1：

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

示例 2：

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

动态规划解题

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
  if (s.length < 2) return 0
  // dp[i]：以第i个字符结尾的最长有效数量
  const dp = Array(s.length).fill(0)
  // 最长有效数量
  let max = 0
  for (let i = 1; i < s.length; i++) {
    // xxxx是有效的，推出xxxx()也是有效的，长度+2
    if (s[i-1] === '(' && s[i] === ')') {
      dp[i] = 2 + (dp[i - 2] || 0)
    }
    // xxxx是有效的，推出(xxxx)也是有效的，长度+2
    else if (s[i] === ')' && dp[i - 1] && s[i - dp[i - 1] - 1] === '(') {
      dp[i] = dp[i - 1] + 2
    }
    // xxxx是有效的，那么xxxxyyyy也是有效的，更新长度
    if (dp[i] && dp[i - dp[i]]) {
      dp[i] = dp[i] + dp[i - dp[i]]
    }
    max = Math.max(max, dp[i])
  }
  return max
};

逻辑解法

在一个有效串中，从左往右，(符号出现的次数一定不会小于)符号的次数

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function(s) {
  if (s.length < 2) return 0
  let max = 0
  let left = 0
  let right = 0
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      left++
    } else {
      right++
    }
    // 不合法，置为0
    if (right > left) {
      left = right = 0
    }
    // 合法，更新长度
    else if (left === right) {
      max = Math.max(max, 2 * right)
    }
  }
  // 上面一个遍历无法处理左括号比右括号多的情况
  // 例如：(()
  // 所以倒序遍历一遍
  left = right = 0
  for (let i = s.length - 1; i > -1; i--) {
    if (s[i] === '(') {
      left++
    } else {
      right++
    }
    if (left > right) {
      left = right = 0
    }
    else if (left === right) {
      max = Math.max(max, 2 * right)
    }
  }
  return max
};