LeetCode 20. 有效的括号：栈的典型应用

一、题目描述（清晰易懂版）

给定一个只包含三种括号的字符串 s，括号类型分别是 '('、')'、'{'、'}'、'['、']'，要求判断这个字符串是否是「有效括号」。

有效括号需要同时满足 3 个条件，缺一不可：

1. 左括号必须用「相同类型」的右括号闭合（比如 '(' 不能用 ']' 闭合）；
2. 左括号必须以「正确的顺序」闭合（比如 "({})" 有效，但 "({)}" 无效，因为括号嵌套顺序乱了）；
3. 每个右括号都有一个「对应的相同类型」的左括号（比如 ")" 单独出现一定无效）。

举几个例子帮助理解：

• 输入 "()" → 输出 true（最简单的有效括号）；
• 输入 "()[]{}" → 输出 true（三种括号依次闭合，顺序正确）；
• 输入 "(]" → 输出 false（左括号类型与右括号不匹配）；
• 输入 "([)]" → 输出 false（嵌套顺序错误）；
• 输入 "{" → 输出 false（只有左括号，没有对应右括号）。

二、解题思路：为什么用「栈」？

这道题的核心痛点是「括号的嵌套顺序」——后出现的左括号，需要先被闭合（类似'先进后出'的逻辑），而栈这种数据结构，恰好完美匹配「先进后出」的特性。

基于栈的解题思路，拆解为 4 步：

1. 初始化一个空栈，用于存储「未闭合的左括号」；
2. 创建一个映射表（对象），存储「右括号对应的左括号」（比如 ')' 对应 '('），这样后续遇到右括号时，能快速找到它需要匹配的左括号；
3. 遍历字符串的每一个字符：
   • 如果当前字符是「左括号」（'('、'['、'{'），就把它压入栈中；
   • 如果当前字符是「右括号」，就检查栈是否为空，以及栈顶元素是否是它对应的左括号：
     • 如果栈为空 → 说明没有未闭合的左括号，却出现了右括号，直接返回 false；
     • 如果栈顶元素不是对应的左括号 → 匹配失败，返回 false；
     • 如果匹配成功 → 把栈顶的左括号弹出（表示这个左括号已经被成功闭合）。
4. 遍历结束后，检查栈是否为空：
   • 栈为空 → 所有左括号都被闭合，返回 true；
   • 栈不为空 → 还有未闭合的左括号，返回 false。

三、完整解题代码（TypeScript 版）

function isValid(s: string): boolean {
    // 1. 初始化空栈，存储未闭合的左括号
    const stack = [];
    
    // 2. 建立右括号与左括号的映射关系，key 是右括号，value 是对应的左括号
    const map: { [key: string]: string } = {
        ')': '(',
        ']': '[',
        '}': '{'
    };
    
    // 3. 遍历字符串的每一个字符
    for (let i = 0; i < s.length; i++) {
        const char: string = s[i];
        
        // 判断当前字符是否是左括号，若是则压入栈中
        if (char === '(' || char === '[' || char === '{') {
            stack.push(char);
        } else {
            // 若当前是右括号，检查栈是否为空 + 栈顶是否匹配
            if (stack.length === 0 || stack[stack.length - 1] !== map[char]) {
                return false;
            }
            // 匹配成功，弹出栈顶的左括号（闭合完成）
            stack.pop();
        }
    }
    
    // 4. 遍历结束后，栈为空则所有括号都闭合，反之则有未闭合的左括号
    return stack.length === 0;
}

四、代码逐行解析（新手必看）

1. 栈的初始化

const stack = []; —— 用一个空数组模拟栈，数组的 push() 方法对应「压栈」，pop() 方法对应「出栈」，stack[stack.length - 1] 可以快速获取「栈顶元素」。

2. 映射表的作用

const map = { ')': '(', ']': '[', '}': '{' } —— 避免用复杂的 if-else 判断右括号对应的左括号。比如遇到 ')' 时，直接通过 map[char] 就能拿到它需要匹配的 '('，简洁高效。

3. 循环遍历的逻辑

遍历字符串的每一个字符，分两种情况处理：

• 左括号：直接压栈，相当于'记录下来，等待闭合'；
• 右括号：先检查「有没有可闭合的左括号」（栈是否为空），再检查「当前右括号和栈顶左括号是否匹配」，只要有一个条件不满足，直接返回 false；匹配成功则出栈，完成一次闭合。

4. 最终判断

return stack.length === 0; —— 这一步很容易被忽略！比如输入 "{{"，遍历结束后栈里还有两个左括号，此时虽然没有遇到不匹配的右括号，但依然是无效括号，所以必须判断栈是否为空。

五、易错点总结（避坑指南）

这道题看似简单，但新手很容易踩坑，整理了 3 个高频易错点：

1. 忘记判断「栈为空」的情况：比如输入 ")"，遍历到右括号时，栈是空的，此时直接返回 false，否则会执行 stack[stack.length - 1]（获取空数组的 -1 索引，结果为 undefined），导致判断错误。
2. 映射表写反键值：比如把 '(' 作为 key，')' 作为 value，这样遇到右括号时，无法通过 map[char] 拿到对应的左括号，会导致匹配失败。
3. 遍历结束后忘记检查栈是否为空：比如输入 "{{"，遍历过程中没有遇到右括号，不会返回 false，但栈不为空，此时必须返回 false，否则会误判为有效括号。

六、复杂度分析（面试加分项）

这道题的时间复杂度和空间复杂度都很优秀，面试时被问到可以从容回答：

• 时间复杂度：O(n) —— 只遍历字符串一次，每个字符的操作（压栈、出栈、判断）都是常数时间，所以总时间和字符串长度 n 成正比。
• 空间复杂度：O(n) —— 最坏情况下，字符串全是左括号（比如 "(((({"），此时栈需要存储所有左括号，栈的长度等于字符串长度 n；最好情况下（字符串为空或有效括号），空间复杂度可以低至 O(1)（空栈）。

七、拓展思考（进阶提升）

这道题是基础款，实际面试中可能会有变形，比如：

1. 字符串中除了括号，还包含其他字符（比如字母、数字、符号），如何判断有效括号？（思路：遍历时分清'括号字符'和'非括号字符'，只对括号字符执行上述逻辑，非括号字符直接跳过即可。）
2. 给定有效括号字符串，计算最长有效括号子串的长度？（这是 LeetCode 32 题，难度提升，依然可以用栈解决，可作为进阶练习参考。）