Skip to content

32-最长有效括号.md

Latest commit

 

History

History
126 lines (99 loc) · 4.16 KB

32-最长有效括号.md

File metadata and controls

126 lines (99 loc) · 4.16 KB
Raw

32-最长有效括号

原题

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

左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

 

示例 1：

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

示例 2：

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

示例 3：

输入：s = ""
输出：0

 

提示：

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

看一下题解 这个题解真是太牛逼了，这个思路是很通用的，需要好好学习总结 正常的思维是我们到第六个的时候，才会知道左括号已经匹配没有了，这时候计算就不太适合了 所以应该让第五个来计算，所以初始添加一个 -1 真是天才的设计啊

思路是理解了，但是有点绕，有没有更好的办法 绕的地方就是在于每次进入 ) 括号分支的时候，需要 pop 一次，这个 pop 有点绕，其他的还好

const longestValidParentheses = function (s) {
    let max = 0;
    let stack = [];
    stack.push(-1);
    
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        
        if (c === '(') {
            stack.push(i);
        }
        else {
            // 这里没有直接检测是否有 (而是直接 pop 是为了让下面的 i push进来，做到一个更换初始值 -1 的作用
            stack.pop();
            if (stack.length) {
                const curMax = i - stack[stack.length - 1];
                max = Math.max(max, curMax);
            }
            else {
                // 充当「参照物」的右括号索引。因为：当左括号匹配光时，栈需要留一个垫底的参照物，用于计算一段连续的有效长度。
                stack.push(i); 
            }
        }
    }
    
    return max;
}

理一下上述解法的思路 0. 核心还是 ) 这个 分支里面的逻辑，这里面有 pop 还有 push 操作，是先 pop 然后 push 的 也就是如果一直是 )，那么每次都会更新 最后一个 ) 的位置 如果有 stack.length 的时候，这时候说明就有 ( push进去了，这时候就可以计算当前的有效括号的长度了

  1. 为什么要先 stack.pop() 然后再检测 stack.length 因为stack.pop() 后，这时候使用 i - stack[stack.length - 1] 就是实际的括号长度了 比如 () 那么在stack里面就是 -1, 0，这时候i = 1的时候，因为把0 pop出去了，这时候就是i - (-1) 就是2，就是括号的实际长度了
  2. 如果 stack没有length了，就需要把当前的i放进去，因为这时候就需要重新开始计算了，之前的有效的括号数已经计算过了

这个是个很规矩的解法，

const longestValidParentheses = function (s) {
  if (s.length === 0) {
    return 0;
  }
  const dp = Array(s.length).fill(0);
  let max = 0;
  for (let i = 1; i < s.length; i++) {
    if (s[i] === ')') {
      if (s[i - 1] === '(') {
        // 2 是一对括号的长度，i - 2 是因为当前的括号是有效括号，所以需要减去2
        dp[i] = 2 + (i - 2 >= 0 ? dp[i - 2] : 0);
      } else if (i - 1 >= 0 && s[i - 1] === ')') {
        // dp[i - 1] 是前面正常匹配的长度，i - 长度，又因为当前的括号是有效括号，所以需要减去1， 得到前面的括号的索引
        const matchIndex = i - dp[i - 1] - 1;
        if (matchIndex >= 0 && s[matchIndex] === '(') {
            // dp[i - 1] + 2 得到有效括号的长度，此时因为
          dp[i] = dp[i - 1] + 2 + (matchIndex - 1 >= 0 ? dp[matchIndex - 1] : 0);
        }
      }
    }
    max = Math.max(max, dp[i]);
  }
  return max;
}

const result = longestValidParentheses("(()");
console.log(result);
const result2 = longestValidParentheses(")()())");
console.log(result2);
const result3 = longestValidParentheses("");
console.log(result3);