DSP56311架构解析：EFCOP协处理器与片上SRAM在实时信号处理中的应用
2026/6/12 20:29:05
一、题目描述
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
- 每个右括号都有一个对应的相同类型的左括号
示例：
| 示例 | 输入 | 输出 |
|---|---|---|
| 示例1 | s = “()” | true |
| 示例2 | s = “()[]{}” | true |
| 示例3 | s = “(]” | false |
| 示例4 | s = “([])” | true |
| 示例5 | s = “([)]” | false |
提示：
- 1 <= s.length <= 10^4
- s 仅由括号 ‘()[]{}’ 组成
二、解题思路总览
拿到这道题，首先思考：什么时候括号是"有效的"？
想象一下括号匹配的过程：
- 遇到左括号 → 它期待一个配对的右括号
- 遇到右括号 → 必须和最近的那个左括号配对
这正是栈（Stack）的经典应用场景：后进先出（LIFO），最近未匹配的那个左括号，恰好应该和当前遇到的右括号配对。
核心思路：
| 步骤 | 操作 | 说明 |
|---|---|---|
| 1 | 遍历字符串s的每个字符 | 从左到右依次处理 |
| 2 | 如果是左括号 ‘(’ ‘[’ ‘{’ | 入栈，等待配对 |
| 3 | 如果是右括号 ‘)’ ‘]’ ‘}’ | 栈顶元素出栈并检查是否匹配 |
| 4 | 遍历结束 | 栈为空 → true；栈非空 → false |
为什么用栈？
| 对比 | 不用栈（错误思路） | 用栈（正确思路） |
|---|---|---|
| 匹配方式 | 盲目查找相同字符 | 只看最近的一个左括号 |
| 顺序要求 | 无法保证"正确的顺序" | 栈天然保证LIFO，匹配顺序正确 |
| 时间复杂度 | O(n^2) 或更差 | O(n) |
三、完整代码（方法一：栈 + STL）
classSolution{public:boolisValid(string s){intn=s.size();// 奇数长度不可能配对成功if(n%2)returnfalse;stack<char>st;for(inti=0;i<n;i++){// 左括号：入栈if(s[i]=='('||s[i]=='['||s[i]=='{'){st.push(s[i]);}else{// 右括号：栈空则匹配失败if(st.empty())returnfalse;chartop=st.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){intn=s.size();if(n%2)returnfalse;// 用数组模拟栈，手动管理指针charst[n];inttop=0;// 栈顶指针，指向下一个待写入位置for(inti=0;i<n;i++){if(s[i]=='('||s[i]=='['||s[i]=='{'){st[top++]=s[i];// 入栈}else{if(top==0)returnfalse;// 栈空charc=st[--top];// 出栈if((s[i]==')'&&c!='(')||(s[i]==']'&&c!='[')||(s[i]=='}'&&c!='{')){returnfalse;}}}returntop==0;}};改进点：用数组替代std::stack，避免STL的函数调用开销和额外的内存分配。
方法三：栈 + HashMap 配对（代码更简洁）
classSolution{public:boolisValid(string s){intn=s.size();if(n%2)returnfalse;stack<char>st;// 用哈希表存储配对关系，代码更清晰unordered_map<char,char>pair={{')','('},{']','['},{'}','{'}};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){intn=s.size();if(n%2)returnfalse;// 统计左括号数量，用于剪枝intcnt_p=0,cnt_s=0,cnt_c=0;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_p<0||cnt_s<0||cnt_c<0)returnfalse;}returncnt_p==0&&cnt_s==0&&cnt_c==0;}};适用范围：此方法只能检测"相邻括号配对"（如"()[]{}"），无法处理嵌套和交叉（如"([])"正确返回 true，但"(]"和"([)]"也会返回 true）。仅作思路拓展，生产代码不推荐。
方法五：字符串替换（直观但低效）
classSolution{public:boolisValid(string s){intn=s.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六、逐行解析（方法一）
intn=s.size();if(n%2)returnfalse;剪枝优化：如果字符串长度是奇数，必然有未配对的括号，直接返回 false。这一步看似简单，但可以跳过大量无效计算。
stack<char>st;数据结构选择：使用std::stack，只关心栈顶元素和入栈/出栈操作。
for(inti=0;i<n;i++){if(s[i]=='('||s[i]=='['||s[i]=='{'){st.push(s[i]);}左括号处理：直接入栈，等待之后可能的配对。
}else{if(st.empty())returnfalse;右括号处理的第一步：如果栈已经空了，说明没有对应的左括号，直接失败。
chartop=st.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开销，极致性能 |
| 方法三：栈+HashMap | O(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栈），代码可读性高且性能足够。