32.最长有效括号

最长有效括号

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

示例 1：

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

示例 2：

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

示例 3：

输入：s = “”
输出：0

提示：

• 0 <= s.length <= $3 * 10^4$
• s[i] 为 ‘(‘ 或 ‘)’

解析

使用栈来解决，栈底始终保持「最后一个没有被匹配的右括号的下标」。

/**
 * @param {string} s
 * @return {number}
 */
var longestValidParentheses = function (s) {
  let max = 0;
  const stack = [-1]; // 初始放入 -1 作为基准

  for (let i = 0; i < s.length; i++) {
    if (s[i] === "(") {
      stack.push(i);
    } else {
      stack.pop();
      if (stack.length === 0) {
        // 栈空了，当前右括号作为新的基准
        stack.push(i);
      } else {
        max = Math.max(max, i - stack[stack.length - 1]);
      }
    }
  }
  return max;
};

栈的巧妙之处在于初始压入 -1，这样当遇到匹配的括号对时，i - stack.top 就是当前有效括号的长度。时间复杂度 O(n)，空间复杂度 O(n)。