手帐 Blog

主题

复盘 · LC 20 有效的括号 ​

题目 ​

题意 ​

给定只含 ()[]{} 的字符串 s，判断括号是否有效：

  • 左括号必须用同类型右括号闭合；
  • 左括号必须以正确顺序闭合；
  • 每个右括号都有对应的左括号。

边界：空串（有效）、奇数长度、开头就是右括号、嵌套 ({[]})、交错错误 ([)]。

涉及算法 ​

标签一句话
栈遇左括号入栈；遇右括号看栈顶是否匹配，匹配则弹出
哈希表右 → 左 的配对表，避免一堆 if

教程对照：10 · 栈。

评价我的解法 ​

思路对：用栈 + 右括号映射到左括号。扫描时「当前右括号恰好匹配栈顶 → 弹出，否则压入」；最后栈空即合法。

我的代码（摘自 20-有效的括号/index.js，不含本地测例）：

javascript
var isValid = function (s) {
  const len = s.length;
  const stack = [];
  const resMap = {
    "]": "[",
    ")": "(",
    "}": "{",
  };
  for (let i = 0; i < len; i++) {
    const top = stack[stack.length - 1];
    const char = s[i];
    if (stack.length > 0 && resMap[char] === top) {
      stack.pop();
    } else {
      stack.push(s[i]);
    }
  }
  return stack.length === 0;
};
  • 正确性：常见用例（含 ([)]、)(、嵌套）都能判对；不匹配的右括号会被压进栈，最终非空 → false。
  • 时间 O(n)，空间 O(n)。
  • 可打磨：
    1. 经典写法是只压左括号；遇右括号时若栈空或不匹配立刻 return false，不必把错误右括号也压进去。
    2. 可先判 s.length % 2 !== 0 直接 false（小优化，非必须）。
    3. resMap 命名略模糊，叫 pairs / match 更直观。

小结：栈题入门答卷合格，面试口述已经能讲清。下一步把「只压左、右不匹配立即失败」练成默写模板即可。

最佳题解 ​

只压左括号，右括号即时校验：

javascript
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
  const pairs = { ")": "(", "]": "[", "}": "{" };
  const stack = [];
  for (const ch of s) {
    if (ch === "(" || ch === "[" || ch === "{") {
      stack.push(ch);
      continue;
    }
    if (stack.length === 0 || stack.pop() !== pairs[ch]) return false;
  }
  return stack.length === 0;
};
  • 时间 O(n)，空间 O(n)。
  • 为何更优：意图更清晰——栈里只有「待匹配的左括号」；非法右括号第一时间失败，少一次「把脏数据压进栈再靠最终长度兜底」。

关联题目 ​

题为何相关
22. 括号生成合法括号的生成版（回溯）
32. 最长有效括号有效括号的 Hard 延伸
1047. 删除字符串中的所有相邻重复项同属「栈消消乐」手感

一句话带走 ​

有效括号：左进栈，右看顶；栈空且全程匹配才合法。