忍者算法

Appearance

探秘括号匹配：从生活场景理解栈的妙用！ ​

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

📚 从生活场景说起 ​

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

💡 问题解析 ​

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

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

示例：

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

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

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

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

🤔 思路发展历程 ​

1. 初学者思路 ​

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

2. 优化思路 ​

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

🚀 优雅的解决方案 ​

java
class Solution {
    public boolean isValid(String s) {
        // 如果字符串长度为奇数，直接返回false
        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 {
                // 遇到右括号时，如果栈为空，说明没有匹配的左括号
                if (stack.isEmpty()) {
                    return false;
                }
                
                // 获取栈顶的左括号
                char left = stack.pop();
                
                // 检查括号是否匹配
                boolean isMatch = (c == ')' && left == '(') ||
                                (c == '}' && left == '{') ||
                                (c == ']' && left == '[');
                                
                if (!isMatch) {
                    return false;
                }
            }
        }
        
        // 最后检查栈是否为空，如果不为空说明有未匹配的左括号
        return stack.isEmpty();
    }
}

📝 代码详解 ​

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

1. 前置优化 ​

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

2. 栈的使用 ​

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

3. 匹配过程 ​

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

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

4. 验证逻辑 ​

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

🎯 易错点剖析 ​

  1. 栈的判空

    • 遇到右括号时，必须先检查栈是否为空
    • 遍历结束后也要检查栈是否为空

  2. 字符匹配

    • 不能只判断括号数量相等
    • 要确保括号类型匹配正确

  3. 处理顺序

    • 遇到右括号时的判断顺序很重要
    • 先检查栈是否为空，再进行匹配

💡 举一反三 ​

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

  1. HTML标签匹配

    • 检查HTML标签是否正确闭合
    • 例如：<div><span></span></div>

  2. 程序代码块匹配

    • 检查代码中的大括号是否配对
    • 可以扩展处理多种括号类型

  3. 表达式求值

    • 在计算表达式时也常用栈来处理括号

🎨 图解演示 ​

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

svg
<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>

🌟 面试技巧 ​

  1. 思路表达

    • 先说明为什么选择使用栈
    • 解释栈的特性如何完美契合题目需求

  2. 代码优化

    • 提到可以用Map存储括号对应关系
    • 讨论空间复杂度的优化可能

  3. 扩展思考

    • 讨论如何处理其他类型的配对问题
    • 考虑如何扩展支持更多种类的括号

🎩 高级优化 ​

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

java
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();
    }
}

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

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

作者：忍者算法 公众号：忍者算法 🎁 回复【刷题清单】获取LeetCode高频面试题合集 🧑‍💻 回复【代码】获取多语言完整题解 💡 回复【加群】加入算法交流群，一起进步 #算法面试 #LeetCode #栈 #字符串

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