【力扣100题】82.有效的括号

一、题目描述给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合左括号必须以正确的顺序闭合每个右括号都有一个对应的相同类型的左括号示例示例输入输出示例1s “()”true示例2s “()[]{}”true示例3s “(]”false示例4s “([])”true示例5s “([)]”false提示1 s.length 10^4s 仅由括号 ‘()[]{}’ 组成二、解题思路总览拿到这道题首先思考什么时候括号是有效的想象一下括号匹配的过程遇到左括号 → 它期待一个配对的右括号遇到右括号 → 必须和最近的那个左括号配对这正是栈Stack的经典应用场景后进先出LIFO最近未匹配的那个左括号恰好应该和当前遇到的右括号配对。核心思路步骤操作说明1遍历字符串s的每个字符从左到右依次处理2如果是左括号 ‘(’ ‘[’ ‘{’入栈等待配对3如果是右括号 ‘)’ ‘]’ ‘}’栈顶元素出栈并检查是否匹配4遍历结束栈为空 → true栈非空 → false为什么用栈对比不用栈错误思路用栈正确思路匹配方式盲目查找相同字符只看最近的一个左括号顺序要求无法保证正确的顺序栈天然保证LIFO匹配顺序正确时间复杂度O(n^2) 或更差O(n)三、完整代码方法一栈 STLclassSolution{public:boolisValid(string s){intns.size();// 奇数长度不可能配对成功if(n%2)returnfalse;stackcharst;for(inti0;in;i){// 左括号入栈if(s[i](||s[i][||s[i]{){st.push(s[i]);}else{// 右括号栈空则匹配失败if(st.empty())returnfalse;chartopst.top();// 检查栈顶左括号是否与当前右括号配对if((s[i])top()||(s[i]]top[)||(s[i]}top{)){st.pop();// 配对成功出栈}else{returnfalse;// 配对失败}}}// 栈空说明全部配对成功returnst.empty()?true:false;}};四、其他解法方法二数组模拟栈手动实现消除STL开销classSolution{public:boolisValid(string s){intns.size();if(n%2)returnfalse;// 用数组模拟栈手动管理指针charst[n];inttop0;// 栈顶指针指向下一个待写入位置for(inti0;in;i){if(s[i](||s[i][||s[i]{){st[top]s[i];// 入栈}else{if(top0)returnfalse;// 栈空charcst[--top];// 出栈if((s[i])c!()||(s[i]]c![)||(s[i]}c!{)){returnfalse;}}}returntop0;}};改进点用数组替代std::stack避免STL的函数调用开销和额外的内存分配。方法三栈 HashMap 配对代码更简洁classSolution{public:boolisValid(string s){intns.size();if(n%2)returnfalse;stackcharst;// 用哈希表存储配对关系代码更清晰unordered_mapchar,charpair{{),(},{],[},{},{}};for(charc:s){if(pair.count(c)){// c 是右括号检查栈顶是否匹配if(st.empty()||st.top()!pair[c]){returnfalse;}st.pop();}else{// c 是左括号入栈st.push(c);}}returnst.empty();}};改进点用unordered_map替代硬编码的 if-else配对关系一目了然扩展性更好比如增加其他括号类型。方法四计数法仅适用于相邻括号配对classSolution{public:boolisValid(string s){intns.size();if(n%2)returnfalse;// 统计左括号数量用于剪枝intcnt_p0,cnt_s0,cnt_c0;for(charc:s){if(c()cnt_p;elseif(c[)cnt_s;elseif(c{)cnt_c;elseif(c))cnt_p--;elseif(c])cnt_s--;elseif(c})cnt_c--;// 剪枝任意计数器为负说明右括号多于左括号if(cnt_p0||cnt_s0||cnt_c0)returnfalse;}returncnt_p0cnt_s0cnt_c0;}};适用范围此方法只能检测相邻括号配对如()[]{}无法处理嵌套和交叉如([])正确返回 true但(]和([)]也会返回 true。仅作思路拓展生产代码不推荐。方法五字符串替换直观但低效classSolution{public:boolisValid(string s){intns.size();if(n%2)returnfalse;// 不断删除相邻的有效括号对直到无法删除while(s.find(())!string::npos||s.find([])!string::npos||s.find({})!string::npos){s.erase(s.find(()),2);s.erase(s.find([]),2);s.erase(s.find({}),2);}returns.empty();}};问题find()是 O(n)erase()是 O(n)整体时间复杂度退化到O(n^3)不可用于生产环境。仅作思路展示。五、算法流程图以输入s ([])为例逐步展示算法执行过程Step 0: 初始状态 s ( [] ) stack: [空] Step 1: 遇到 (左括号入栈 s ( [] ) ^ stack: [ ( ] Step 2: 遇到 [左括号入栈 s ( [] ) ^ stack: [ ( , [ ] Step 3: 遇到 ]右括号 - 栈顶是 [匹配成功 - pop s ( [] ) ^ stack: [ ( ] Step 4: 遇到 )右括号 - 栈顶是 (匹配成功 - pop s ( [] ) ^ stack: [空] Step 5: 遍历结束 stack为空 → 返回 true再来看一个失败案例s ([)]Step 0: 初始状态 s ( [ ) ] stack: [空] Step 1: 遇到 (入栈 s ( [ ) ] ^ stack: [ ( ] Step 2: 遇到 [入栈 s ( [ ) ] ^ stack: [ ( , [ ] Step 3: 遇到 )右括号 - 栈顶是 [但 ) 应该匹配 ( - 不匹配返回 false s ( [ ) ] ^ stack: [ ( , [ ] 最终结果: false六、逐行解析方法一intns.size();if(n%2)returnfalse;剪枝优化如果字符串长度是奇数必然有未配对的括号直接返回 false。这一步看似简单但可以跳过大量无效计算。stackcharst;数据结构选择使用std::stack只关心栈顶元素和入栈/出栈操作。for(inti0;in;i){if(s[i](||s[i][||s[i]{){st.push(s[i]);}左括号处理直接入栈等待之后可能的配对。}else{if(st.empty())returnfalse;右括号处理的第一步如果栈已经空了说明没有对应的左括号直接失败。chartopst.top();if((s[i])top()||(s[i]]top[)||(s[i]}top{)){st.pop();}else{returnfalse;}}}配对检查核心逻辑。当前右括号必须与栈顶的左括号类型一致才算配对成功。returnst.empty()?true:false;最终判断遍历结束后栈空说明所有左括号都成功配对栈非空说明有左括号没被匹配。七、复杂度分析各方法复杂度对比方法时间复杂度空间复杂度说明方法一STL栈O(n)O(n)标准解法稳定高效方法二数组模拟栈O(n)O(n)省去STL开销极致性能方法三栈HashMapO(n)O(n)代码简洁配对关系清晰方法四计数法O(n)O(1)错误解法仅适用于相邻配对方法五字符串替换O(n^3)O(n)不可用复杂度太高方法一详细复杂度分析时间复杂度O(n)只需遍历字符串一次每个字符最多入栈一次、出栈一次空间复杂度O(n)最坏情况全部是左括号如 “(((((”栈中最多存放 n/2 个元素严谨分析但渐进表示为 O(n)补充说明情况栈中元素数量说明全部左括号O(n)“(((((”全部右括号O(1)第一步就返回false交替出现O(1)“()()()” 每次配对后栈即空八、面试追问 FAQ问题回答要点Q1: 为什么不使用队列队列是FIFO先进先出而括号匹配需要LIFO。最近的左括号才应该被匹配队列无法提供这个能力。Q2: 可以不用栈吗理论上可以用递归模拟栈但会增加函数调用开销且有栈溢出风险。不推荐。Q3: 如果要返回具体错误信息怎么办可以在返回false时增加额外逻辑记录是多余右括号、“多余左括号还是类型不匹配”。Q4: 如何处理带优先级的表达式求值这是另一个经典问题通常用两个栈一个存操作数一个存操作符。括号匹配只是其中一步。Q5: 如果字符串很长10^6级别怎么办当前算法O(n)已经最优主要瓶颈可能在I/O。可以用内存映射或流式处理但核心算法不变。Q6: 三种栈的实现哪个更好生产环境优先用方法一STL栈代码可读性高如果在竞赛或极端性能场景用方法二数组模拟方法三适合需要频繁扩展配对规则的场景。九、相关题目题号题目难度关联点32最长有效括号困难栈的延伸应用921使括号有效的最少添加中等栈的变形1021删除最外层的括号简单栈的变形1541平衡括号的最少插入中等栈的变形推荐刷题顺序本题20.有效的括号→ 基础921使括号有效的最少添加→ 变形1021删除最外层的括号→ 变形32最长有效括号→ 综合十、总结维度内容考察知识点栈Stack的应用难度简单代码框架遍历 栈操作关键技巧利用栈的LIFO特性保证匹配顺序边界情况奇数长度、栈空、右括号不匹配变形题返回最小插入数、最长有效长度推荐解法方法一STL栈或方法二数组模拟一句话总结括号匹配是栈的入门经典题核心就是最近未匹配的左括号 当前右括号应该匹配的对象用栈的LIFO特性天然实现这个逻辑。生产代码推荐使用方法一STL栈代码可读性高且性能足够。