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

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

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

示例 3： 输入：s = “” 输出：0

示例4： 输入：s=”((())” 输出：4

提示：

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

方法

暴力

动态规划

怎么定义dp[i]？
我们试着拆分子问题，目光盯着子问题与大问题之间的联系
感受一下“提供”这词：前一个子问题的解可以“提供”给后一个子问题多大的有效长度。后一个子问题的解，要想纳入前面“提供”的有效长度，则前面子串的末尾必须是有效子串的一部分。（连续性）
子问题dp[i]：以s[i]为结尾的子串中，所形成的最长有效子串的长度，且有效子串是以s[i]为结尾。
规定有效子串是以s[i]为结尾，这样才能“提供”给后一个子问题一段有效长度
紧盯子问题与大问题之间的联结点

关注联结点：子串的末位s[i]，它要么是’(‘，要么是’)’：

  • s[i]是’(‘，以它为结尾的子串，肯定不是有效括号子串——dp[i] = 0
  • s[i]是’)’，以它为结尾的子串可能是有效子串，还需考察前一个子问题的末尾s[i-1]
    • s[i-1]是’(‘，s[i-1]和s[i]组成一对，有效长度保底为 2，还需考察s[i-2]：
      • s[i-2]不存在，则有效长度只有 2——dp[i] = 2
      • s[i-2]存在，则加上以s[i-2]为结尾的最长有效长度——dp[i]=dp[i-2]+2
    • s[i-1]是’)’，s[i-1]和s[i]是’))’，以s[i-1]为结尾的最长有效长度为dp[i-1]，跨过这个长度（具体细节不用管，总之它最大能提供dp[i-1]长度），来看s[i-dp[i-1]-1]这个字符：
      • s[i-dp[i-1]-1]不存在或为’)’，则s[i]找不到匹配，直接gg——dp[i]=0
      • s[i-dp[i-1]-1]是’(‘，与s[i]匹配，有效长度 = 2 + 跨过的dp[i-1]+ 前方的dp[i-dp[i-1]-2]。等一下，s[i-dp[i-1]-2]要存在才行！：
        • s[i-dp[i-1]-2]存在，dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
        • s[i-dp[i-1]-2]不存在，dp[i] = dp[i-1] + 2

base case ：dp[0] = 0 一个括号形成不了有效子串

  1. /**
  2.  * @param {string} s
  3.  * @return {number}
  4.  */
  5. const longestValidParentheses = (s) => {
  6.   let maxLen = 0;
  7.   const len = s.length;
  8.   const dp = new Array(len).fill(0);
  9.   for (let i = 1; i < len; i++) {
  10.     if (s[i] == ')') {
  11.       if (s[i - 1] == '(') {
  12.         if (i - 2 >= 0) {
  13.           dp[i] = dp[i - 2] + 2;
  14.         } else {
  15.           dp[i] = 2;
  16.         }
  17.       } else if (s[i - dp[i - 1] - 1] == '(') {
  18.         if (i - dp[i - 1] - 2 >= 0) {
  19.           dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
  20.         } else {
  21.           dp[i] = dp[i - 1] + 2;
  22.         }
  23.       }
  24.     }
  25.     maxLen = Math.max(maxLen, dp[i]);
  26.   }
  27.   return maxLen;
  28. };

复杂度分析

  • 时间复杂度：O（n）
  • 空间复杂度：O（n）

⭐️栈

思路
用一个栈来检查括号的有效性，用一个数组 valid 来记录匹配括号对的位置。

栈的用法跟20.有效括号里的一样，不过入栈的不是 (，而是它们的下标。
在遍历过程中，如果碰到 )，就从栈中弹出一个元素，这个元素就是 ) 对应的 ( 的下标。
接着我们在 valid 中这两个下标对应的位置做个标识 1，说明这里找到了一对有效括号。
等遍历结束之后，在 valid 中找到连续最长的 1 序列。
算法

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
    const valid = Array(s.length).fill(0);
    const stack = [];

    for (let i = 0; i < s.length; i++) {
        if (s[i] === '(') stack.push(i);
        if (s[i] === ')' && stack.length > 0) {
            // Mark the open and close indices as 1 in valid.
            valid[i] = 1;
            valid[stack.pop()] = 1;
        }
    }

    // Find longest sequence of 1s.
    let count = 0,
        max = 0;
    for (let v of valid) {
        v && count++;
        v || (count = 0); // v为0时，count就为0,就能算出count的值
        max = Math.max(max, count);
    }
    return max;
};

复杂度分析

  • 时间复杂度：O(n)，n 为字符串的长度。
  • 空间复杂度：O(n)，n 为字符串的长度。

知识点

  • stack.pop()返回数组最后一个元素

正向逆向结合/不需要额外的空间