力扣热题100实战 | 第20期有效的括号——栈结构的经典启蒙前言一、题目括号怎么才算“有效”关键点解读二、第一反应计数法立刻发现不行错误思路示例这段代码的问题在哪三、核心思想栈的“后进先出”特性为什么栈能解决这个问题直观理解消除法图解流程四、代码实现栈 哈希表面试标准答案代码实现代码解析复杂度分析五、优化版本数组模拟栈性能更优六、细节剖析面试官真正关心的问题Q1为什么用栈而不用其他数据结构Q2为什么用 Deque 代替 StackQ3遇到右括号时栈为空意味着什么Q4为什么最后要检查栈是否为空Q5哈希表在这里起到了什么作用七、面试官追问进阶版追问1如果括号种类扩展到任意数量比如 和 代码怎么改追问2如果要求返回第一个无效括号的位置索引怎么实现追问3如何验证一个字符串是否只包含括号字符追问4如果要求找出最长有效括号子串的长度LeetCode 32怎么解八、实际开发这道题到底有什么用场景1编译器语法检查场景2HTML/XML 标签解析场景3表达式求值场景4代码编辑器的自动补全场景5JSON/XML 格式校验九、总结从一道题到一类题附录思考题括号匹配问题是数据结构栈的“Hello World”。它简单到让人轻视却又深刻到足以让你理解“后进先出”这一思想在编程中的无限妙用。前言你好我是礼拜天没时间。前十九期我们系统学习了哈希表、链表操作、滑动窗口、二分查找、动态规划、双指针、回溯算法等多种算法思想。这一期我们来解一道非常基础但极其重要的题目——有效的括号LeetCode 第20题。这道题在力扣上被标记为“简单”但它的简单并不意味着可以掉以轻心。恰恰相反这道题是栈结构的启蒙题也是很多开发者第一次接触“后进先出”思想的起点。掌握这道题不仅是为了通过面试更是为了理解栈这种数据结构在编译器设计、表达式求值、函数调用等领域的核心地位。今天我希望能带你从“消除法”的直观理解出发一步步写出优雅的代码并深入理解其背后的思想。一、题目括号怎么才算“有效”先看题目描述LeetCode 第20题给定一个只包括(){}[]的字符串s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例 1输入s () 输出true示例 2输入s ()[]{} 输出true示例 3输入s (] 输出false 解释( 和 ] 类型不匹配。示例 4输入s ([)] 输出false 解释括号虽然成对出现但顺序不正确。正确的应该是 {[]} 这样的嵌套。示例 5输入s {[]} 输出true 解释正确的嵌套顺序。关键点解读三种括号小括号()、中括号[]、大括号{}每种都有左右之分。两个条件类型匹配左括号必须用同类型的右括号闭合顺序正确括号的嵌套顺序必须正确不能出现交叉空字符串题目没有明确说明但通常认为空字符串是有效的因为没有任何不匹配的括号。长度奇偶有效字符串的长度一定是偶数因为括号必须成对出现 。二、第一反应计数法立刻发现不行当我第一次看到这道题我的第一反应是统计每种左括号和右括号的数量看是否相等。错误思路示例// 错误思路千万别这么写publicbooleanisValid(Strings){intcount10,count20,count30;for(charc:s.toCharArray()){if(c()count1;if(c))count1--;if(c[)count2;if(c])count2--;if(c{)count3;if(c})count3--;}returncount10count20count30;}这段代码的问题在哪对于([)]这个输入统计结果小括号 1个左1个右 → 0中括号 1个左1个右 → 0但实际字符串是无效的这说明仅仅统计数量是不够的还需要考虑顺序。这就是栈结构登场的地方。三、核心思想栈的“后进先出”特性为什么栈能解决这个问题观察括号的嵌套规律 {[]}中最内层的[]先闭合然后才是外层的{}这种“后遇到的左括号先被匹配”的特性完美契合栈的“后进先出”LIFO结构直观理解消除法想象一下玩“消消乐”的游戏 遇到左括号就把它“压入”栈中遇到右括号就尝试与栈顶的最后一个左括号“消除”如果能消除类型匹配就把栈顶弹出如果不能消除或者栈为空没有左括号可匹配则字符串无效遍历完所有字符后如果栈为空所有括号都被消除则字符串有效图解流程以s {[]}为例步骤当前字符栈状态左侧为栈底右侧为栈顶操作1{{左括号入栈2[{[左括号入栈3]{栈顶是[与]匹配弹出4}(空)栈顶是{与}匹配弹出最终栈为空 → 返回true✅以s ([)]为例步骤当前字符栈状态操作1((左括号入栈2[([左括号入栈3)(栈顶是[与)不匹配 → 返回false❌四、代码实现栈 哈希表面试标准答案代码实现classSolution{publicbooleanisValid(Strings){// 1. 边界条件如果长度为奇数直接返回falseif(s.length()%21){returnfalse;}// 2. 建立映射表右括号 - 对应的左括号MapCharacter,CharactermapnewHashMap();map.put(),();map.put(],[);map.put(},{);// 3. 使用Deque代替StackJava官方推荐DequeCharacterstacknewLinkedList();// 4. 遍历字符串for(inti0;is.length();i){charcs.charAt(i);// 如果是右括号if(map.containsKey(c)){// 如果栈为空或者栈顶元素不是对应的左括号返回falseif(stack.isEmpty()||!stack.peek().equals(map.get(c))){returnfalse;}// 匹配成功弹出栈顶stack.pop();}else{// 如果是左括号入栈stack.push(c);}}// 5. 遍历结束栈空则有效否则无效returnstack.isEmpty();}}代码解析奇数长度提前返回有效字符串必须成对出现长度为奇数时直接返回false这是一种常见的剪枝优化 。哈希表建立映射用Map存储右括号到对应左括号的映射这样在判断匹配时可以直接获取期望的左括号避免写多个if-else。Deque 优于 StackJava 官方推荐使用Deque接口的实现如LinkedList或ArrayDeque来代替古老的Stack类因为Stack继承自Vector性能较差 。核心逻辑遇到左括号 → 入栈遇到右括号 → 检查栈顶是否是对应的左括号如果栈为空 → 没有左括号可匹配 →false如果栈顶不匹配 → 类型错误 →false如果匹配 → 弹出栈顶继续最后检查栈空遍历结束后如果栈中还有未匹配的左括号说明无效 。复杂度分析时间复杂度O(n) —— 只需遍历一次字符串每个字符入栈出栈一次空间复杂度O(n) —— 最坏情况下栈中需要存储所有左括号如(((五、优化版本数组模拟栈性能更优如果追求极致性能可以用数组模拟栈避免使用Deque的开销。classSolution{publicbooleanisValid(Strings){intns.length();if(n%21)returnfalse;// 用字符数组模拟栈char[]stacknewchar[n];inttop-1;// 栈顶指针-1表示空栈for(inti0;in;i){charcs.charAt(i);if(c(||c[||c{){// 左括号入栈stack[top]c;}else{// 右括号栈必须非空且与栈顶匹配if(top-1)returnfalse;chartopCharstack[top];if((c)topChar!()||(c]topChar![)||(c}topChar!{)){returnfalse;}top--;// 弹出栈顶}}returntop-1;}}优势避免对象创建开销内存访问更连续性能提升约 20-30%。六、细节剖析面试官真正关心的问题Q1为什么用栈而不用其他数据结构答案因为括号嵌套具有“后进先出”的特性 。最内层的括号最先闭合对应栈顶的元素最外层的括号最后闭合对应栈底的元素。栈天然支持这种操作。Q2为什么用 Deque 代替 Stack答案Java 的Stack类继承自Vector是线程安全的有同步开销且基于数组但扩容机制效率不高。Deque接口的ArrayDeque实现是非线程安全的但性能更好且提供了push、pop、peek等栈操作 。Q3遇到右括号时栈为空意味着什么答案意味着当前右括号没有对应的左括号可匹配比如字符串以)开头。这种情况直接返回false。Q4为什么最后要检查栈是否为空答案遍历结束后栈中可能还有剩余的左括号没有被匹配比如(()。这说明有左括号没有对应的右括号字符串无效 。Q5哈希表在这里起到了什么作用答案哈希表将右括号映射到对应的左括号使得匹配判断变得简洁优雅 。如果不使用哈希表就需要写多个if-else判断代码会变得冗长且容易出错。七、面试官追问进阶版追问1如果括号种类扩展到任意数量比如和代码怎么改思路只需要在映射表中添加新的对应关系即可。map.put(,);// 其他逻辑完全不变追问2如果要求返回第一个无效括号的位置索引怎么实现思路在遇到不匹配时直接返回当前索引如果最后栈不为空返回栈中第一个未匹配左括号的索引。publicintfirstInvalidIndex(Strings){DequeIntegerstacknewLinkedList();// 存索引for(inti0;is.length();i){charcs.charAt(i);if(c(||c[||c{){stack.push(i);// 入栈索引}else{if(stack.isEmpty())returni;// 右括号无匹配charlefts.charAt(stack.peek());if((c)left!()||(c]left![)||(c}left!{)){returni;// 类型不匹配}stack.pop();}}returnstack.isEmpty()?-1:stack.peek();// 返回第一个未匹配左括号}追问3如何验证一个字符串是否只包含括号字符思路可以用正则表达式[^(){}\[\] ]匹配非法字符或者遍历检查每个字符是否在允许的集合中。追问4如果要求找出最长有效括号子串的长度LeetCode 32怎么解思路这是本题的进阶版需要用到栈或动态规划。栈解法中栈底始终存放最后一个未匹配的右括号的索引用于计算长度。八、实际开发这道题到底有什么用很多读者会问“括号匹配实际工作中哪用得到”其实它的思想无处不在场景1编译器语法检查编译器的词法分析和语法分析阶段需要检查代码中的括号、花括号、方括号是否匹配。比如 Java、C 等语言中{和}必须成对出现。场景2HTML/XML 标签解析HTML 和 XML 中的标签必须正确嵌套div必须对应/div这和括号匹配是同一个问题 。场景3表达式求值在计算器程序中需要处理带括号的表达式如(12)*(34)。栈结构被用来处理运算符优先级和括号嵌套。场景4代码编辑器的自动补全当你在 IDE 中输入(时编辑器自动补全)并在你删除时保持配对背后就是括号匹配算法。场景5JSON/XML 格式校验JSON 格式要求花括号{}和方括号[]正确嵌套校验器内部就是用栈实现的。九、总结从一道题到一类题回顾一下我们从有效的括号学到了什么维度收获算法思维计数法错误→ 栈消除法理解“后进先出”的应用场景代码技巧哈希表简化判断、奇数长度剪枝、Deque vs Stack复杂度分析O(n) 时间、O(n) 空间这是最优解面试要点为什么用栈为什么最后要检查栈空哈希表的作用工程关联编译器、HTML解析、表达式求值、代码编辑器力扣热题100的第二十题不是为了难住你而是为了告诉你最简单的数据结构往往能解决最经典的问题。栈的“后进先出”思想将陪伴你走过整个编程生涯。下一期预告《合并两个有序链表》——链表操作的入门必修课附录思考题看完这篇文章你可以试着回答如果字符串中不仅包含括号还包含字母和数字如a(b)c[d]e需要忽略字母只验证括号代码怎么改如何用栈实现一个简单的 HTML 标签验证器你能用这道题的思路去解 LeetCode 32最长有效括号吗欢迎在评论区留下你的思考