2022-05-31 《leetcode》 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

方案1 栈

var longestValidParentheses1 = function (s) {
  let stack = [];
  let match = new Array(s.length).fill(0);
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      stack.push(i);
    } else {
      if (stack.length) {
        stack.pop();
      } else {
        match[i] = 1;
      }
    }
  }
  for (let i = 0; i < stack.length; i++) {
    match[stack[i]] = 1;
  }
  let count = 0;
  let max = 0;
  for (let i = 0; i < match.length; i++) {
    if (match[i] === 1) {
      max = max > count ? max : count;
      count = 0;
    } else {
      count++;
    }
  }
  max = max > count ? max : count;
  return max;
};

方案2 动态规划

var longestValidParentheses2 = function (s) {
  if (s.length < 2) {
    return 0;
  }
  // 定义 dt 数组，置0
  let dt = new Array(s.length).fill(0);
  for (let i = 1; i < s.length; i++) {
    if (s[i] === ")") {
      if (s[i - 1] === "(") {
        // 示例： ()() [0, 2, 0, 4]
        // 4 = dt[i - 2] + 2
        dt[i] = (i >= 2 ? dt[i - 2] : 0) + 2;
      } else if (i > dt[i - 1] && s[i - dt[i - 1] - 1] === "(") {
        // (()) [0, 0, 2, ]
        // 当i=3时： i - dt[i - 1] - 1 = 0; s[0] = (

        // ()(()) [0, 2, 0, 0, 2, ]
        // 当 i = 5时：(i - dt[i - 1] - 2 >= 0 ? dt[i - dt[i - 1] - 2] : 0)
        // 前面还有连续未加入，则需要加入
        dt[i] = dt[i - 1] + 2 + (i - dt[i - 1] - 2 >= 0 ? dt[i - dt[i - 1] - 2] : 0);
      }
    }
  }
  return Math.max(...dt);
};