Heading

32.最长有效括号 (opens new window)

Tags: algorithms string dynamic-programming

Langs: c cpp csharp dart elixir erlang golang java javascript kotlin php python python3 racket ruby rust scala swift typescript

• algorithms
• Hard (37.73%)
• Likes: 2465
• Dislikes: -
• Total Accepted: 431.6K
• Total Submissions: 1.1M
• Testcase Example: '"(()"'

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

 

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

 

提示：

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

/*
 * @lc app=leetcode.cn id=32 lang=javascript
 *
 * [32] 最长有效括号
 * 栈
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  let result = 0

  let i = 0
  while (i < s.length) {
    if (s[i] === '(') {
      const stack = []
      let current = 0
      for (let j = i; j < s.length; j++) {
        if (s[j] === '(') {
          stack.push(s[j])
          current++
        } else {
          if (stack.length === 0) {
            result = Math.max(result, current)
            current = 0
            break
          } else {
            stack.pop()
            current++
            if (stack.length === 0) {
              result = Math.max(result, current)
            }
          }
        }
      }
    }
    i++
  }
  return result
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=32 lang=javascript
 *
 * [32] 最长有效括号
 * 贪心  以当前字符结尾，计算最大长度
 */

// @lc code=start
/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  let max = 0

  let left = 0
  let right = 0
  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      left++
    } else if (s[i] === ')') {
      right++
    }
    if (right > left) {
      left = 0
      right = 0
    } else if (left === right) {
      max = Math.max(max, left * 2)
    }
  }
  left = 0
  right = 0
  for (let i = s.length - 1; i >= 0; i--) {
    if (s[i] === '(') {
      left++
    } else if (s[i] === ')') {
      right++
    }
    if (left > right) {
      left = 0
      right = 0
    } else if (left === right) {
      max = Math.max(max, left * 2)
    }
  }

  return max
}
// @lc code=end