括号匹配

如何判断括号字符串是否有效？

• 目标 (20): 每种左括号都必须被同类型右括号按正确顺序闭合;
• 前置剪枝: 长度为奇数直接返回 false;
• 做法: 遇到左括号就压入它对应的右括号, 遇到右括号则与栈顶比较;
• 结束条件: 遍历完栈必须为空;

const isValid = (s) => {
  if (s.length % 2 === 1) return false;
  const pairs = { "(": ")", "{": "}", "[": "]" };
  const stack = [];
  for (const char of s) {
    if (pairs[char] != null) stack.push(pairs[char]);
    else if (char !== stack.pop()) return false;
  }
  return stack.length === 0;
};

• 时间 $O(n)$, 空间 $O(n)$;

如何求最长有效括号子串的长度？

• 栈的语义: 栈底存放"当前有效子串起点的前一个下标", 最初压入 -1;
• 遇左括号: 压入其下标;
• 遇右括号: 先弹栈; 弹空说明该右括号无法匹配, 把它的下标压回作新起点基准; 否则当前长度是 i - stack.at(-1);
• 时间 $O(n)$, 空间 $O(n)$;

const longestValidParentheses = (s) => {
  const stack = [-1];
  let res = 0;
  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 res = Math.max(res, i - stack.at(-1));
    }
  }
  return res;
};