[!info] related notes 算法面试题型 MOC 栈

有效括号

题目链接：https://leetcode.cn/problems/valid-parentheses/

题型判断

本题判断整个字符串是否有效，输入按题意只包含 ()[]{} 六种括号；它不是查找最长有效子串，后者见 最长有效括号。

关键信号：

• 遇到右括号时，要找最近一个还没匹配的左括号
• 匹配关系天然是“最近未匹配优先”

所以直接用栈维护左括号。

核心思路

• 遇到左括号：入栈
• 遇到右括号：检查栈顶是不是对应左括号
  • 不是 -> 直接返回 false
  • 是 -> 弹栈
• 遍历结束后，栈必须为空

易错点

• 栈空时不能直接取栈顶
• 遍历完以后别忘了检查栈是不是空
• 多种括号时最好统一维护映射表

JavaScript

var isValid = function(s) {
    const stack = [];
    const map = {
        ')': '(',
        ']': '[',
        '}': '{'
    };

    for (const ch of s) {
        if (ch === '(' || ch === '[' || ch === '{') {
            stack.push(ch);
        } else {
            if (!stack.length || stack[stack.length - 1] !== map[ch]) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.length === 0;
};

一句话总结

右括号匹配的是最近未匹配的左括号。时间 O(n)，栈最坏 O(n)；只有数量相等不够，例如 ([)] 仍因嵌套顺序错误而无效。