20. 有效的括号#

今天我们来聊一道经典的算法题 - LeetCode 20「有效的括号」。这道题虽然看起来简单，却蕴含着栈这个数据结构的精髓，是我非常喜欢用来讲解栈的入门题目。

📚 从生活场景说起#

想象你在阅读一本书，遇到了很多层嵌套的括号。作为读者，你是如何确保括号的配对是正确的呢？其实我们的大脑在处理这个问题时，就像一个栈一样工作：每当看到一个左括号，就在心里”压入”一个期待；看到右括号时，就和最近的那个未配对的左括号进行匹配。今天我们就用代码来实现这个过程！

问题描述#

题目目标#

给定一个只包含 (、)、{、}、[、] 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。

示例 1#

输入： s = "()[]{}" 输出： true 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 问题解析#

题目要求：给定一个只包括 ’(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s，判断字符串是否有效。有效字符串需要满足：

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

示例：

输入：s = "()"
输出：true

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

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

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

java

🤔 思路发展历程#

1. 初学者思路#

很多初学者会想到用计数的方法：统计左右括号的数量是否相等。但这种方法无法处理 ”([)]” 这样的错误情况。

2. 优化思路#

我们需要考虑括号的匹配顺序。栈的特点是”后进先出”，正好符合括号匹配的规则：最后出现的左括号应该最先被匹配。

🚀 优雅的解决方案#

class Solution {
    public boolean isValid(String s) {
        // 边界条件：如果总长度是奇数，括号不可能两两配对，直接判定无效
        if (s.length() % 2 != 0) {
            // 只要出现这种情况就无需继续遍历
            return false;
        }

        // 栈：用于存放尚未匹配的左括号（后进先出，正好匹配最近的左括号）
        Stack<Character> stack = new Stack<>();

        // 逐个扫描字符串中的字符
        for (char c : s.toCharArray()) {
            // 如果是左括号，先入栈等待后续右括号来匹配
            if (c == '(' || c == '{' || c == '[') {
                // 压栈：记录一个“待匹配”的左括号
                stack.push(c);
            } else {
                // 走到这里说明 c 是右括号；若栈为空，表示没有可配对的左括号
                if (stack.isEmpty()) {
                    // 提前出现右括号，字符串必定无效
                    return false;
                }

                // 弹出最近的左括号，与当前右括号尝试配对
                char left = stack.pop();

                // 判断当前这对括号是否类型一致
                boolean isMatch = (c == ')' && left == '(') ||
                                (c == '}' && left == '{') ||
                                (c == ']' && left == '[');

                // 只要有一对不匹配，整串就无效
                if (!isMatch) {
                    return false;
                }
            }
        }

        // 全部遍历结束后：栈必须为空（否则还有未被匹配的左括号）
        return stack.isEmpty();
    }
}

java

📝 代码详解#

让我们深入理解这个解决方案的每个环节：

1. 前置优化#

我们首先通过检查字符串长度是否为偶数来快速排除一些无效情况。这是因为有效的括号字符串必须是成对的。

2. 栈的使用#

栈的使用是这个解决方案的核心。我们用栈来记录所有出现的左括号，这样在遇到右括号时，就可以和最近的左括号进行匹配。

3. 匹配过程#

对于每个字符，我们有两种处理方式：

如果是左括号，直接压入栈中
如果是右括号，将其与栈顶的左括号进行匹配

4. 验证逻辑#

在遍历完成后，我们还需要检查栈是否为空。这是因为可能存在未匹配的左括号。

🎯 易错点剖析#

栈的判空
- 遇到右括号时，必须先检查栈是否为空
- 遍历结束后也要检查栈是否为空
字符匹配
- 不能只判断括号数量相等
- 要确保括号类型匹配正确
处理顺序
- 遇到右括号时的判断顺序很重要
- 先检查栈是否为空，再进行匹配

💡 举一反三#

这道题的思路可以扩展到很多类似场景：

HTML标签匹配
- 检查HTML标签是否正确闭合
- 例如：<div><span></span></div>
程序代码块匹配
- 检查代码中的大括号是否配对
- 可以扩展处理多种括号类型
表达式求值
- 在计算表达式时也常用栈来处理括号

🎨 图解演示#

为了帮助大家更好地理解栈的工作原理，我准备了一个可视化的示例：

<svg viewBox="0 0 800 400" xmlns="http://www.w3.org/2000/svg">
  <!-- 背景 -->
  <rect width="800" height="400" fill="#f8f9fa"/>

  <!-- 字符串显示区域 -->
  <g transform="translate(50,50)">
    <text x="0" y="0" font-size="16">输入字符串: "( { [ ] } )"</text>

    <!-- 字符框 -->
    <g transform="translate(0,20)">
      <rect x="0" y="0" width="40" height="40" fill="none" stroke="#1976d2" stroke-width="2"/>
      <text x="20" y="25" text-anchor="middle" font-size="20">(</text>

      <rect x="50" y="0" width="40" height="40" fill="none" stroke="#1976d2" stroke-width="2"/>
      <text x="70" y="25" text-anchor="middle" font-size="20">{</text>

      <rect x="100" y="0" width="40" height="40" fill="none" stroke="#1976d2" stroke-width="2"/>
      <text x="120" y="25" text-anchor="middle" font-size="20">[</text>

      <rect x="150" y="0" width="40" height="40" fill="none" stroke="#1976d2" stroke-width="2"/>
      <text x="170" y="25" text-anchor="middle" font-size="20">]</text>

      <rect x="200" y="0" width="40" height="40" fill="none" stroke="#1976d2" stroke-width="2"/>
      <text x="220" y="25" text-anchor="middle" font-size="20">}</text>

      <rect x="250" y="0" width="40" height="40" fill="none" stroke="#1976d2" stroke-width="2"/>
      <text x="270" y="25" text-anchor="middle" font-size="20">)</text>
    </g>
  </g>

  <!-- 栈的可视化 -->
  <g transform="translate(50,150)">
    <text x="0" y="0" font-size="16">栈的变化过程：</text>

    <!-- 栈容器 -->
    <rect x="0" y="20" width="100" height="200" fill="none" stroke="#388e3c" stroke-width="2"/>

    <!-- 栈内元素（从下到上） -->
    <g transform="translate(0,200)">
      <rect x="10" y="-40" width="80" height="30" fill="#c8e6c9"/>
      <text x="50" y="-20" text-anchor="middle">(</text>

      <rect x="10" y="-80" width="80" height="30" fill="#c8e6c9"/>
      <text x="50" y="-60" text-anchor="middle">{</text>

      <rect x="10" y="-120" width="80" height="30" fill="#c8e6c9"/>
      <text x="50" y="-100" text-anchor="middle">[</text>
    </g>
  </g>

  <!-- 操作说明 -->
  <g transform="translate(200,150)">
    <text x="0" y="30" font-size="14">1. 遇到 '(' 压入栈</text>
    <text x="0" y="60" font-size="14">2. 遇到 '{' 压入栈</text>
    <text x="0" y="90" font-size="14">3. 遇到 '[' 压入栈</text>
    <text x="0" y="120" font-size="14">4. 遇到 ']' 弹出 '['</text>
    <text x="0" y="150" font-size="14">5. 遇到 '}' 弹出 '{'</text>
    <text x="0" y="180" font-size="14">6. 遇到 ')' 弹出 '('</text>
  </g>
</svg>

plaintext

🌟 面试技巧#

思路表达
- 先说明为什么选择使用栈
- 解释栈的特性如何完美契合题目需求
代码优化
- 提到可以用Map存储括号对应关系
- 讨论空间复杂度的优化可能
扩展思考
- 讨论如何处理其他类型的配对问题
- 考虑如何扩展支持更多种类的括号

🎩 高级优化#

如果你想让代码更优雅，可以使用HashMap来存储括号对应关系：

class Solution {
    public boolean isValid(String s) {
        // 边界剪枝：奇数长度不可能完全匹配
        if (s.length() % 2 != 0) return false;

        // 映射表：记录“右括号 -> 对应左括号”，便于统一匹配逻辑
        Map<Character, Character> brackets = new HashMap<>();
        // ')' 必须匹配 '('
        brackets.put(')', '(');
        // '}' 必须匹配 '{'
        brackets.put('}', '{');
        // ']' 必须匹配 '['
        brackets.put(']', '[');

        // 栈中存放尚未匹配的左括号
        Stack<Character> stack = new Stack<>();

        // 逐字符处理输入串
        for (char c : s.toCharArray()) {
            // 不在映射表中的字符一定是左括号，直接入栈等待匹配
            if (!brackets.containsKey(c)) {
                stack.push(c);
            // 在映射表中说明是右括号：栈空或类型不一致都应直接失败
            } else if (stack.isEmpty() || stack.pop() != brackets.get(c)) {
                return false;
            }
        }

        // 所有字符处理后，栈为空才说明全部左括号都被成功匹配
        return stack.isEmpty();
    }
}

java

这个优化版本的代码有以下优点：

更容易扩展支持新的括号类型
代码更简洁清晰
逻辑判断更统一

通过这篇文章，我们不仅学会了如何使用栈来解决括号匹配问题，更重要的是理解了为什么栈这种数据结构特别适合处理这类配对问题。这种思维方式对于解决其他类似的算法问题也很有帮助。如果你对这个题目还有任何疑问，欢迎在评论区讨论！