[!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;
};

一句话总结

右括号匹配的一定是最近那个还没被匹配的左括号，这就是栈。