【Java算法入门】有效的括号问题，栈的经典应用！✨

在这里插入图片描述

前言

亲爱的同学们，大家好！👋 今天我要和大家分享一个算法面试中的经典问题——有效的括号。这个问题不仅是力扣（LeetCode）上的热门题目，也是各大公司技术面试的常客，更是学习栈这种数据结构的绝佳案例！🌟

还记得我第一次教这个问题时，很多同学都感到困惑："括号匹配看起来这么简单，为什么需要用到栈这种数据结构呢？"其实，这正是算法之美所在——用优雅的方式解决看似简单但实际复杂的问题。

今天，我将用最通俗易懂的语言，带领大家一步步攻克这个经典问题，彻底掌握栈的应用技巧。无论你是算法初学者还是准备面试的同学，这都是一个值得深入理解的问题。准备好了吗？让我们一起开始这段算法之旅吧！🚀

知识点说明

问题描述

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

有效字符串需满足：

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

例如：

• 输入：s = “()”
• 输出：true
• 输入：s = “()[]{}”
• 输出：true
• 输入：s = “(]”
• 输出：false
• 输入：s = “([)]”
• 输出：false
• 输入：s = “{[]}”
• 输出：true

栈（Stack）数据结构

栈是一种遵循后进先出（LIFO, Last In First Out）原则的线性数据结构。想象一下叠放的盘子，你只能从最上面取盘子，也只能在最上面放新盘子。栈的基本操作包括：

• push：将元素添加到栈顶
• pop：移除并返回栈顶元素
• peek（或top）：查看栈顶元素但不移除
• isEmpty：检查栈是否为空

在Java中，我们可以使用java.util.Stack类或java.util.Deque接口的实现类（如LinkedList或ArrayDeque）来实现栈。

算法思路

解决有效括号问题的核心思路是：

1. 遍历字符串中的每个字符
2. 如果是左括号（(, {, [），则将其推入栈中
3. 如果是右括号（), }, ]），则从栈中弹出一个元素，并检查它是否与当前右括号匹配
   • 如果匹配，继续处理下一个字符
   • 如果不匹配，或者栈为空（没有左括号可以匹配），则字符串无效
4. 遍历完成后，如果栈为空（所有左括号都有匹配的右括号），则字符串有效；否则无效

重难点说明

1. 括号匹配的核心原理 🔍

括号匹配问题的核心在于"最近相关性"——最近遇到的左括号应该与最近遇到的右括号匹配。这种"最近相关性"正是栈结构的特点，这也是为什么栈是解决这类问题的理想选择。

2. 处理不同类型的括号 🔄

在有效括号问题中，我们需要处理三种不同类型的括号：圆括号()、方括号[]和花括号{}。这就要求我们不仅要检查括号的开闭顺序，还要确保括号的类型匹配。

一个常用的技巧是使用哈希表（或映射）来存储括号对应关系，例如：

Map<Character, Character> brackets = new HashMap<>();
brackets.put(')', '(');
brackets.put('}', '{');
brackets.put(']', '[');

这样，当我们遇到右括号时，可以快速查找它应该匹配的左括号。

3. 边界情况处理 ⚠️

在实现算法时，我们需要特别注意以下边界情况：

• 空字符串（通常认为是有效的）
• 只有左括号或只有右括号的字符串
• 字符串长度为奇数（一定无效，因为括号必须成对出现）
• 字符串以右括号开始（一定无效，因为没有左括号可以匹配）

4. 栈的实现选择 🛠️

在Java中，我们有多种方式实现栈：

• 使用java.util.Stack类（传统但不推荐，因为它是线程安全的，性能较低）
• 使用java.util.Deque接口的实现类，如ArrayDeque（推荐，性能更好）
• 自定义栈实现

选择合适的实现方式可以提高算法的效率。

核心代码说明

让我们一步步实现这个算法：

import java.util.Stack;
import java.util.HashMap;
import java.util.Map;

public class ValidParentheses {
    
    /**
     * 判断字符串中的括号是否有效
     * @param s 包含括号的字符串
     * @return 如果括号有效返回true，否则返回false
     */
    public static boolean isValid(String s) {
        // 如果字符串长度为奇数，一定不是有效的括号
        if (s.length() % 2 != 0) {
            return false;
        }
        
        // 创建一个栈用于存储左括号
        Stack<Character> stack = new Stack<>();
        
        // 创建括号对应关系的映射
        Map<Character, Character> bracketMap = new HashMap<>();
        bracketMap.put(')', '(');
        bracketMap.put('}', '{');
        bracketMap.put(']', '[');
        
        // 遍历字符串中的每个字符
        for (char c : s.toCharArray()) {
            // 如果是右括号
            if (bracketMap.containsKey(c)) {
                // 如果栈为空或栈顶元素与当前右括号不匹配
                if (stack.isEmpty() || stack.pop() != bracketMap.get(c)) {
                    return false;
                }
            } 
            // 如果是左括号，推入栈中
            else {
                stack.push(c);
            }
        }
        
        // 如果栈为空，说明所有括号都匹配
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        // 测试用例
        String[] testCases = {"()", "()[]{}", "(]", "([)]", "{[]}"};
        
        for (String test : testCases) {
            boolean result = isValid(test);
            System.out.println("\"" + test + "\" 是有效的括号吗？ " + result);
        }
    }
}

使用ArrayDeque优化版本

import java.util.Deque;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;

public class ValidParenthesesOptimized {
    
    public static boolean isValid(String s) {
        // 如果字符串长度为奇数，一定不是有效的括号
        if (s.length() % 2 != 0) {
            return false;
        }
        
        // 使用ArrayDeque代替Stack，性能更好
        Deque<Character> stack = new ArrayDeque<>();
        
        // 创建括号对应关系的映射
        Map<Character, Character> bracketMap = new HashMap<>();
        bracketMap.put(')', '(');
        bracketMap.put('}', '{');
        bracketMap.put(']', '[');
        
        for (char c : s.toCharArray()) {
            if (bracketMap.containsKey(c)) {
                // 如果栈为空或栈顶元素与当前右括号不匹配
                if (stack.isEmpty() || stack.pop() != bracketMap.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }
        
        return stack.isEmpty();
    }
}

代码执行过程可视化

让我们以 s = "{[]}" 为例，可视化算法的执行过程：

1. 初始状态：
   • stack = []（空栈）
   • bracketMap = {‘)’ -> ‘(’, ‘}’ -> ‘{’, ‘]’ -> ‘[’}
2. 遍历字符 ‘{’：
   • ‘{’ 是左括号，将其推入栈中
   • stack = [‘{’]
3. 遍历字符 ‘[’：
   • ‘[’ 是左括号，将其推入栈中
   • stack = [‘{’, ‘[’]
4. 遍历字符 ‘]’：
   • ‘]’ 是右括号，从栈中弹出一个元素，得到 ‘[’
   • 检查 ‘[’ 是否与 ‘]’ 匹配（通过查找 bracketMap[‘]’] = ‘[’）
   • 匹配成功，继续处理下一个字符
   • stack = [‘{’]
5. 遍历字符 ‘}’：
   • ‘}’ 是右括号，从栈中弹出一个元素，得到 ‘{’
   • 检查 ‘{’ 是否与 ‘}’ 匹配（通过查找 bracketMap[‘}’] = ‘{’）
   • 匹配成功，继续处理下一个字符
   • stack = []（空栈）
6. 遍历结束，检查栈是否为空：
   • stack 为空，所有括号都匹配
   • 返回 true

算法复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。我们需要遍历字符串中的每个字符一次。
• 空间复杂度：O(n)，在最坏情况下（例如，字符串中只包含左括号），我们需要将所有字符推入栈中。

对Java初期学习的重要意义

学习"有效的括号"这个问题对Java初学者有以下几点重要意义：

1. 栈数据结构的实际应用 📚

这个问题是栈这种数据结构的经典应用场景。通过这个问题，你可以：

• 理解栈的"后进先出"特性
• 学习如何在Java中使用栈（Stack或Deque）
• 体会数据结构如何帮助我们解决实际问题

2. 算法思维的培养 🧠

解决有效括号问题需要你：

• 分析问题的本质（最近相关性）
• 选择合适的数据结构（栈）
• 处理各种边界情况

这些都是培养算法思维的好练习，有助于提升你的问题解决能力。

3. Java集合框架的实践 🛠️

这个问题让你有机会实践Java集合框架中的多个组件：

• Stack类或Deque接口
• HashMap类
• 字符串处理

通过实际应用，你可以更好地理解这些API的用法和特点。

4. 代码实现能力的提升 💻

实现这个算法需要你：

• 正确处理循环和条件判断
• 理解字符串和字符的操作
• 编写清晰、简洁的代码

这些都是编程实践中非常重要的能力。

5. 面试准备的基础 🎯

这个问题是技术面试中的常见题目，掌握它可以：

• 增强你的面试信心
• 展示你对基本数据结构的理解
• 为学习更复杂的算法问题打下基础

总结

亲爱的同学们，今天我们一起学习了如何使用栈来解决有效括号问题。💯

让我们回顾一下关键点：

1. 栈是解决括号匹配问题的理想数据结构，因为它的"后进先出"特性完美契合了括号的嵌套规则。
2. 算法的核心思想是遇到左括号就入栈，遇到右括号就出栈并检查是否匹配。这种简洁的思路体现了算法的优雅之处。
3. 边界情况的处理也很重要，包括空字符串、奇数长度字符串等特殊情况。
4. 在Java中，我们可以使用Stack类或ArrayDeque类来实现栈，后者通常性能更好。

有效括号问题看似简单，却蕴含着丰富的算法思想。它就像是数据结构世界的"Hello World"，简单却包含了编程的精髓。🌟

通过学习这个问题，你不仅掌握了一个经典算法，更重要的是，你学会了如何使用合适的数据结构来解决特定问题。这种思维方式将在你的编程之路上不断发挥作用。

记住，算法学习是一个循序渐进的过程，每解决一个问题，你就向成为一名优秀的程序员迈进了一步！✨

喜欢这篇文章的话，别忘了点赞、收藏、分享哦！有任何问题也欢迎在评论区留言讨论！👋