【栈】LC 20.有效的括号-北京尧图网络

文章目录前言一、题目1、原题链接2、题目描述二、个人思路整理1、思路分析2、解题代码三、知识风暴前言本专栏文章为《LeetCode 热题 100》的刷题题解相关内容如有侵权立即删除。一、题目1、原题链接20.有效的括号2、题目描述二、个人思路整理1、思路分析利用栈遇到左括号将其直接压入栈中遇到右括号首先判断栈是否为空。若为空说明没有对应的左括号直接返回false若栈不为空弹出栈顶元素检查是否与当前右括号类型匹配。若不匹配返回false。遍历结束后检查栈是否为空。若栈为空说明所有左括号都已匹配返回true否则返回false。复杂度分析时间复杂度O ( n ) O(n)O(n)一个for循环每个字符最多进栈一次、出栈一次其中n nn为字符串 s 的长度。空间复杂度O ( n ) O(n)O(n)开辟辅助栈空间。2、解题代码classSolution{public:boolisValid(string s){// 奇数长度字符串不可能满足直接返回falseif(s.size()%2){returnfalse;}stackcharst;for(inti0;is.size();i){// 遇到左括号直接入栈if(s[i](||s[i][||s[i]{){st.push(s[i]);}else{// 遇到右括号对其是否匹配进行判断// 如果栈为空说明没有对应的左括号if(st.empty()){returnfalse;}// 检查栈顶元素是否匹配if(s[i])st.top()(||s[i]]st.top()[||s[i]}st.top(){){st.pop();// 匹配成功则出栈左括号}else{returnfalse;// 如果存在左、右括号不匹配直接返回false这个判断分支必须要有否则会导致后续逻辑混乱甚至出错}}}returnst.empty();}};三、知识风暴关于检查栈顶元素是否匹配时若不写else条件导致的后果以下为大模型相关解释防止遗忘以输入s ([}}])为例处理前 2 个字符(和[依次入栈此时栈内元素为[(, []栈顶是 ‘[’。处理第 3 个字符}右大括号触发else分支进入if(s[i] ) ... || s[i] } st.top() {)判断。因为当前栈顶是[条件不成立所以没有执行st.pop()。关键错误点代码没有写else { return false; }因此程序忽略了这个错误继续执行循环处理第 4 个字符}右大括号再次进入判断此时栈顶依然是[条件仍不成立再次跳过。处理第 5 个字符]右中括号触发判断s[i] ] st.top() [条件成立执行 st.pop()将[弹出栈。处理第 6 个字符)右圆括号触发判断s[i] ) st.top() (条件成立执行st.pop()将(弹出栈。循环结束此时栈为空st.empty()为true最终代码返回了true但实际应为false。

【栈】LC 20.有效的括号

相关推荐

免费风扇控制软件FanControl实操指南：三步让机箱安静下来

Windows 11 越来越卡？Win11Debloat 一键系统优化与隐私清理终极指南

Visual C++ 运行库报错不用慌：AIO 工具一行命令装齐 6 大版本

更多资讯

OpenCV 4.5.5工业部署指南：DNN一致性、编译避坑与静态SDK封装

3D结构语义化：让大模型真正‘看懂’CAD与网格数据

YOLOv5+ArcFace双阶段解耦：检测不精准为何识别仍鲁棒？

Windows下Flash Attention编译与优化实战

AI科研idea生成：从模糊兴趣到可判定问题的四步流水线

GEO入门指南：从RAG架构到结构化数据标记的AI搜索优化实操

今日更新

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？