Vue.js

Appearance

On this page

实战：有效的括号 ​

这是栈最经典的应用题——括号匹配。

题目描述 ​

LeetCode 20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合
  2. 左括号必须以正确的顺序闭合

示例：

输入：s = "()[]{}"
输出：true

输入：s = "(]"
输出：false

解法 ​

核心思想：

  • 遇到左括号：入栈
  • 遇到右括号：检查栈顶是否是对应的左括号
    • 是 → 出栈
    • 否 → 返回 false
  • 最后检查栈是否为空
javascript
function isValid(s) {
    const stack = [];
    const pairs = {
        ')': '(',
        ']': '[',
        '}': '{'
    };
    
    for (const char of s) {
        if (char === '(' || char === '[' || char === '{') {
            // 左括号入栈
            stack.push(char);
        } else {
            // 右括号：检查栈顶
            if (stack.length === 0 || stack[stack.length - 1] !== pairs[char]) {
                return false;
            }
            stack.pop();
        }
    }
    
    return stack.length === 0;
}

执行过程 ​

s = "([{}])"

遍历过程：
字符 '('：左括号，入栈 → stack: ['(']
字符 '['：左括号，入栈 → stack: ['(', '[']
字符 '{'：左括号，入栈 → stack: ['(', '[', '{']
字符 '}'：匹配 '{'，出栈 → stack: ['(', '[']
字符 ']'：匹配 '['，出栈 → stack: ['(']
字符 ')'：匹配 '('，出栈 → stack: []

栈为空，返回 true

三种无效情况 ​

1. 右括号多余："]"
   遇到 ']' 时栈为空 → 返回 false

2. 括号不匹配："(]"
   栈顶是 '('，但遇到 ']' → 不匹配

3. 左括号多余："(()["
   遍历结束后栈不为空 → 返回 false

复杂度 ​

  • 时间：O(n)，遍历一次
  • 空间：O(n)，最坏情况栈存储所有字符

本章小结 ​

有效的括号是栈的经典应用：

  1. 左括号入栈：等待匹配
  2. 右括号匹配：检查栈顶
  3. 最后检查：栈必须为空

括号匹配的思想可以扩展到很多场景：HTML 标签匹配、表达式解析等。

在 GitHub 上编辑此页