算法学习day3–有效括号栈配对解法引入为什么「有效括号」值得一学括号匹配是编译器、IDE、Lint 工具每天都在做的事你写下一行代码编辑器立刻能标出「这里少了一个右括号」。这道 LeetCode 第 20 题看似简单却是**栈Stack**这一数据结构最经典的应用入门题——它把「最近打开的结构必须最先关闭」这个 LIFO后进先出思想讲得明明白白。学会它你就掌握了函数调用栈、撤销操作、浏览器前进后退等一整类问题的思维模型。题目回顾给定一个只包含(、)、[、]、{、}的字符串s判断字符串是否有效。有效需满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合每个右括号都有一个对应的同类型左括号。例如()、()[]{}、([])是有效的(]、([)]、(((是无效的。核心知识点三种无效情况用栈分析后无效字符串恰好可以归为三类判断逻辑必须三条全覆盖才算正确无效情况示例表现遇到右括号时栈为空)(没有左括号可配栈顶类型不符(]、([)]交叉嵌套顺序错误遍历结束后栈非空(((有左括号没被闭合一个常见的误区是把右括号也入栈——实际上右括号永远不会入栈它只负责和栈顶左括号「对账」。另一个常见遗漏是第三种情况很多人只判断了遍历过程中的配对忘了最后检查栈是否为空导致(((被误判为有效。关键技巧入栈时压「期望的右括号」实现时有两种写法写法一哈希表映射。用mapOf() to (, ] to [, } to {)记录「右括号 → 对应左括号」遇到右括号时弹栈比对。写法二直接压期望的右括号推荐。遇到左括号时不压它自己而是把它对应的右括号压入栈。这样遇到右括号时只需判断「栈顶是否等于当前字符」连查表都省了代码更短、出错面更小funisValid(s:String):Boolean{// 左括号 - 期望的右括号valpairsmapOf((to),[to],{to})valstackArrayDequeChar()for(cins){if(pairs.containsKey(c)){// 左括号压入它「期望匹配」的右括号stack.addLast(pairs[c]!!)}else{// 右括号栈空或栈顶不符立即失败if(stack.isEmpty()||stack.removeLast()!c)returnfalse}}// 第三种无效情况还有左括号没闭合returnstack.isEmpty()}逐段拆解ArrayDequeChar在 Kotlin 中作栈使用addLast/removeLast均为 O(1)左括号分支压入期望的右括号后续配对变成纯字符比较右括号分支用「短路」写法stack.isEmpty() || removeLast() ! c一行同时覆盖前两种无效情况函数末尾stack.isEmpty()补上第三种情况。复杂度分析时间复杂度 O(n)每个字符最多入栈、出栈各一次空间复杂度 O(n)最坏情况全是左括号如((((()栈中要存下所有字符。对比暴力解法——每次扫描找一对()/[]/{}替换为空串直到无法替换最坏 O(n²)且代码繁琐。计数法分别统计三类括号数量更不可行它无法检测顺序([)]数量完全正确却是无效串。这也是为什么这道题「非栈不可」只有栈能记住嵌套的顺序。一个具体走查s ([])读(压入期望的)栈为[)]读[压入期望的]栈为[)],[]]栈顶是]读]栈顶正是]弹出栈为[)]读)栈顶正是)弹出栈空结束且栈空 → 有效。实际应用场景编译器 / 解释器语法分析阶段检查括号、引号、代码块的花括号是否正确闭合IDE 与编辑器输入)时高亮匹配的(本质就是维护一个括号栈XML / HTML 校验标签嵌套ab/b/a与括号嵌套同构把「压期望的右括号」换成「压期望的结束标签」即可复用撤销操作 / 调用栈同样是 LIFO——最近发生的事最先被回退。可迁移套路这道题沉淀下来的是一个通用模板「最近未完成的事用一个栈来记遇到新事件时与栈顶对账」。凡是问题中出现「嵌套」「配对」「最近匹配」这类字眼先想栈。判断逻辑务必自查三条栈空遇右、栈顶不符、结束后栈非空——三者缺一就会有反例。小结有效括号 三种无效情况全不发生缺一不可栈是「顺序配对」问题的标准解法LIFO 天然对应嵌套结构「压期望的右括号」是简化代码的经典小技巧把查表比较变成纯字符比较时间 O(n)、空间 O(n)优于暴力的 O(n²)计数法因无法感知顺序而出局。