企业官网建设流程全解析

刷算法题最怕的一种状态，就是看题觉得很简单，一提交发现全是边界问题。今天的训练营打卡内容就是典型：20. 有效的括号 和 1047. 删除字符串中的所有相邻重复项，两道题都属于“字符串处理 + 栈”的入门组合，代码量都不大，但几乎每个训练营群里都会有人翻车。我这次把两道题连在一起刷，最大的收获是抓住了它们共用的一个思考方式——用栈做“回退”。这篇文章会把解题过程、易错点、以及我自己总结的栈题套路完整过一遍，也希望给正在刷算法题的朋友一点参考。

如果你刚开始学数据结构，栈这个概念可能很抽象。但这两道题恰恰能把栈讲明白：一个讲“匹配”，一个讲“消除”，本质上都依赖“后进先出”这个特性。题目本身不算难，难的是从“看着简单”到“一次写对”之间那段路，而这正是训练营里最值得复盘的部分。

1. 为什么“栈”是这两道题共同的主角

1.1 从处理顺序看本质

先别急着写代码，想一个问题：有效的括号里，最内层的括号一定是最先被匹配的。比如"{[]}"，虽然左花括号{最早出现，但它要等到最后的}才匹配；而中间的[和]反而先配对。这种“后进先出”的顺序，和栈完全一致。

1047 题也一样。删除相邻重复项时，假设字符串是"abbac"，你先看到a，然后看到两个b，消掉bb之后，新的末尾变成了a，结果下一个a又和它重复，继续消。你发现没有——每次消除后，需要回头重新比较的，永远是“最近还没被处理掉的那个字符”。这个“最近的一个”，恰恰就是栈顶。

所以这两道题虽然名字不同，一个讲括号合法性，一个讲字符串去重，但骨子里是同一个模型：我都会用一个容器把暂时没法决定去留的元素缓存起来，等新元素出现时，优先跟最近缓存的元素比一比。

1.2 一个“回头看”的判断标准

我自己刷题有个习惯，看到一个新题目，先不翻题解，而是问三个问题：

• 处理当前元素时，需不需要知道上一个还没处理完的元素？
• 如果上一个元素暂时不能决定去留，能不能先存起来？
• 后面某一步，会不会反过来用到这个“最近”的元素？

只要这三个问题里大多是“是”，那这道题八成要用栈。拿 20 题举例：遇到一个右括号时，你要判断它能不能闭合最近的左括号；如果最近那个左括号不匹配，整个字符串就无效。这完全符合“回头看”的定义。1047 题就更直接了，当前字符就是要跟上一个还没被消除的字符比，比完要么压栈要么弹栈。

这也是为什么我不建议死记“栈适合解决括号匹配”“栈适合解决表达式求值”这种结论。结论记多了，题目稍微变形就懵了。记住“是否依赖最近未处理元素”这个判断标准，比记住十道题都管用。

1.3 队列为什么不能直接替代

有一点值得拎出来说清楚：为什么这两道题不用队列？既然训练营标题是“栈与队列”，很多初学者会想，队列不也能存元素吗？

关键区别在比较对象。队列是先进先出，队头是最早进来的元素；而这两道题每次都比较“最近的元素”。如果你用队列，弹出的永远是老早以前进来的字符，完全对不上。比如括号匹配时，出现右括号}时，你需要看的是最近一个未匹配的左括号，而不是最先出现的那个左括号。这是栈的天然主场。

队列当然也有自己的人生，比如 BFS 遍历、滑动窗口、消息队列削峰，那些场景强调“先来先处理”。栈和队列不是同一个工具，服务的是两种相反的需求。先把这两道题吃透，后面再对比队列时，你会非常清楚“为什么不能用栈实现一个排队系统”。

2. 20. 有效的括号：一份匹配清单的三种典型错法

2.1 先弄清楚什么才叫“有效”

题目给的是只有()[]{}的字符串，要判断括号是否有效。有效条件其实就两条：

• 左括号必须被同类型的右括号闭合；
• 左括号必须以正确的顺序闭合。

第二条最容易忽略。([)]这种字符串，每个括号类型都有，左右数量也对，但顺序是错的，因为[先于(出现，却要在(之前闭合，这就是交叉嵌套，无效。我把这种字符串当面试时的必考题，因为它专门用来拆穿“只数个数不看顺序”的写法。

还有几个边界想清楚：

• 空字符串返回 true；
• 只有左括号，比如((，false；
• 只有右括号，比如]]，false；
• 长度是奇数，直接 false，因为括号一定是成对的。

2.2 三种典型错法，你多半中过招

先说第一种：三个计数器。有人用count1、count2、count3分别记录三种括号，遇到左加一，遇到右减一，最后检查是否全为 0。这个写法对()[]{}有效，但对([)]完全失效，因为计数器永远不会出现负数，最后也是 0，可字符串是无效的。原因就是计数器丢了“顺序”信息。

第二种：遇到右括号直接弹栈，但不检查栈空。比如字符串")"或"())"，第一个字符就是右括号，此时栈还是空的，你直接st.pop()就崩了，或者访问栈顶报错。即使语言里不报错，逻辑上也必须判 false，因为没有任何左括号能跟这个右括号匹配。所以记住：访问栈顶或弹出之前，永远先问一句“栈空了吗”。

第三种：循环结束后忘记检查栈是否为空。比如"(()"，遍历完所有字符后，栈里还剩下一个(，说明这个左括号没有被闭合，当然是 false。很多人写代码时注意力全放在循环里，觉得循环跑完就完事了，结果在最后一步栽跟头。

2.3 一种更不容易写错的写法：压入“期待值”

常见的思路是：遇到左括号就压入左括号，遇到右括号再拿它跟栈顶比较。这种做法没问题，但需要维护一个映射表，代码会多一些。

我更喜欢另一个写法：遇到左括号时，直接压入它对应的右括号。比如遇到(压入)，遇到[压入]，遇到{压入}。这样等到遇到右括号时，只需要做一件事：检查栈顶是不是当前这个字符。是就弹出，不是就返回 false。

这个写法的好处有两个。第一，少写一层 map 查询，字符直接跟字符比较，逻辑更直白。第二，判断条件集中在一个方向：遇到右括号时，栈空说明没有可匹配的左括号；栈顶不相等说明类型不匹配或顺序错误。我个人在实际刷题中比较推荐这种套路，尤其在白板面试时，代码短，思路清楚。

2.4 完整代码和复杂度分析

C++ 版本我用 std::stack：

bool isValid(string s) { if (s.size() % 2 == 1) return false; stack<char> st; for (char c : s) { if (c == '(') { st.push(')'); } else if (c == '[') { st.push(']'); } else if (c == '{') { st.push('}'); } else { if (st.empty() || st.top() != c) { return false; } st.pop(); } } return st.empty(); }

Python 版本可以用 list 模拟：

def isValid(s: str) -> bool: if len(s) % 2 == 1: return False stack = [] for ch in s: if ch == '(': stack.append(')') elif ch == '[': stack.append(']') elif ch == '{': stack.append('}') else: if not stack or stack[-1] != ch: return False stack.pop() return not stack

时间复杂度 O(n)，每个字符最多入栈一次、出栈一次。空间复杂度 O(n)，最坏情况是字符串全是左括号，比如"(((((("，所有字符全压进栈里。这里可以加一个小优化：如果字符串长度是奇数，直接返回 false，连遍历都不用。虽然理论上复杂度还是 O(n)，但能省掉一半跑到最后的开销。

3. 1047. 删除字符串中的所有相邻重复项：把“消消乐”写进循环

3.1 为什么暴力替换的做法不可行

先看一个经典例子："abba"。直观上，先删掉相邻的"bb"，剩下"aa"，这两个又相邻重复，得继续删，最后结果是空串。

如果你用常规的循环 replace，比如while ("aa" in s or "bb" in s ...)，会面临两个问题。第一，你可能只替换一次就退出循环，漏掉了删除后产生的新重复，结果返回"aa"，判错。第二，每次 replace 都要重新扫描整个字符串，如果有连续触发连锁消除，最坏复杂度会变成 O(n²)，在字符串很长时就很难受了。

这个例子正好暴露了问题的本质：删除一对相邻重复之后，新暴露出来的字符可能又和更前面的字符重复，所以需要一种机制能回到“前一个字符”继续比较。这已经明明白白告诉你，要用栈。

3.2 核心过程：扫描、比较、弹出、回退

我用"abbaca"完整走一遍，题目要求的输出是"ca"：

• 读入a，栈空，直接压入，栈为[a]；
• 读入b，栈顶是a，不相等，压入，栈为[a, b]；
• 读入b，栈顶是b，相等，弹出，栈为[a]；
• 读入a，栈顶是a，相等，弹出，栈为[]；
• 读入c，栈空，压入，栈为[c]；
• 读入a，栈顶是c，不相等，压入，栈为[c, a]。

最后把栈里的字符拼起来，得到"ca"。

注意第三步到第四步的过程：弹出的瞬间，相当于把刚才存入的那个b撤销了，随后新读入的a自动跟更早的a比较。这个“撤销后再比较”的动作，就是栈题里最迷人的地方。它看起来像是回头走了一步，但栈帮你把这个回头动作做成了 O(1) 的常数时间操作。

3.3 三种实现方式，从朴素到优化

第一种，Python 的 list 模拟栈：

def removeDuplicates(s: str) -> str: stack = [] for ch in s: if stack and stack[-1] == ch: stack.pop() else: stack.append(ch) return ''.join(stack)

这个写法最简单，逻辑一目了然，适合作为第一版答案。

第二种，C++ 直接用 string 当作栈。因为 string 本身就支持push_back、pop_back、back这些操作，天然就是 char 类型的栈：

string removeDuplicates(string s) { string result; for (char c : s) { if (!result.empty() && result.back() == c) { result.pop_back(); } else { result.push_back(c); } } return result; }

这个做法有个额外好处：最后返回的就是栈本身，不需要再做一次拼接。

第三种，原地双指针优化。既然栈里的内容就是结果字符串，而且题目允许修改原字符串，那么可以用一个 write 指针模拟栈的大小，把原数组当成栈空间。扫描时，如果当前字符和s[write-1]相等，说明栈顶和当前字符重复，write--表示弹出；否则把当前字符写到s[write]位置，然后write++。最后把字符串截断到 write 长度：

string removeDuplicates(string s) { int write = 0; for (char c : s) { if (write > 0 && s[write - 1] == c) { write--; } else { s[write++] = c; } } s.resize(write); return s; }

这个版本空间复杂度为 O(1)，只用了几个整型变量，不额外开辟栈空间。它本质上是“用数组手写了一个栈”。我建议你先把朴素写法搞懂，再来看这个优化，不要一上来就用地板优化，否则容易看不懂。

3.4 时间空间与调试心得

时间复杂度 O(n)，空间复杂度根据实现方式不同，朴素版 O(n)，双指针版 O(1)。

这块我吃过一次亏，说说调试心得。刚开始写的时候，我习惯在循环里打印当前字符和栈顶，但需要注意的是，不能只盯着“相等就弹出”这个分支。真正容易出问题的是“栈空时”的情况：如果栈是空的，访问stack[-1]会越界，所以在判断时一定要把stack非空放在前面，写成if stack and stack[-1] == ch，Python 里顺序不能反，C++ 里同样要先判断!result.empty()。很多人一上来就写if (result.back() == ch)，遇到空栈就去访问，直接崩掉。

还有一个细节是大小写敏感性。题目里没说忽略大小写，所以'A'和'a'不算重复。刷题时别自己给题目加条件，这属于读题不仔细的锅。

4. 两道题一起刷，我总结出的栈题解题模板

4.1 四步拆题法

把这两道题放在一起复盘，我提取出一个可复用的思考流程，暂时叫它“四步拆题法”。

第一步，判断场景：处理当前元素时，需不需要跟“之前出现过的最近元素”做比较？需要，就往栈上想。

第二步，确定栈的语义：栈里存什么？20 题存的是“期待的右括号”，也可以存左括号；1047 题存的是“还没被消除的字符”。语义不同，代码结构完全不同。有些题存索引，有些题存数值，还有些题存计数器。

第三步，写清入栈出栈条件：什么时候压入？什么时候弹出？这一步是代码核心，尽量写成条件分支，别混在同一个 if 里。

第四步，想结果怎么还原：栈最后是中间结果，怎么变成真正的答案？20 题要求返回布尔值，直接看栈空不空；1047 题要返回字符串，需要把栈拼起来，或者直接用 string 当栈，连拼接都省了。

我把两道题整理成一张对照表：

这样一比较，你会发现两道题的本质非常接近：都是当前元素和栈顶比较，相等就走“消除/匹配”路线，不相等就走“入栈”路线。只是 20 题需要额外处理“三种类型括号”的映射关系。

4.2 判空是栈题的命门

刷了这么多栈题，我最想强调的一点是判空。几乎所有栈相关的 bug，都是从“访问了不存在的栈顶”开始的。

我见过太多类似的代码：遇到右括号，直接st.pop()，忘了先检查st.empty()；看到栈不为空，但忘记循环结束后还要检查；或者在栈顶比较时，不判断栈是否为空，导致 undefined behavior。这类问题在 LeetCode 上不一定每次都崩，因为语言和编译器不同，表现也不太一样，但逻辑一定是错的。

我给自己定了一条规则：写任何栈题，凡是涉及top、pop、back的操作，先写判空。哪怕这题不可能出现空栈访问，也要保留判断，因为代码的可读性和防御性比少写一行更重要。面试时这个习惯非常加分，它说明你考虑过边界。

4.3 用数组或字符串代替标准栈的实用技巧

一开始刷题时，我默认用语言自带的 stack 类，后来发现不少场景里用数组或字符串模拟栈更顺手。

先说 C++。std::stack 是一个容器适配器，默认底层是 std::deque，操作上有push、pop、top。但如果你最终要按顺序输出栈内元素，stack 的遍历并不方便，得先把元素倒腾到另一个容器里。相反，用 vector 或 string 模拟栈，既能当栈用，又保留了顺序访问的能力。1047 题直接返回 string 当栈，就是这种思路的极致体现。

Python 里同理，list 本身就是最好的栈，append 和 pop 都是 O(1)，还能直接遍历。很多从 Java 转过来的人习惯去 import Stack 类，其实没必要。Java 官方也不推荐再用 Stack 类，更建议用 ArrayDeque。语言细节因环境而异，但核心思想一样：普通栈操作，用动态数组模拟，效率高、可控性好。

当然，如果元素类型比较复杂，比如需要存(字符, 出现次数)这种 pair，直接用一个 stack<pair<char, int>> 或者 vector<pair<int, int>> 都可以。只要你能保证压入和弹出的顺序符合“最近优先”，用什么容器反而不重要。

5. 进阶一击：这两道题的常见变形

5.1 从“有效的括号”出发的三条升级路线

20 题后面通常接着三道题，难度逐步上升，我建议按这个顺序刷。

第一道是 22. 生成括号。它要求生成所有有效的括号组合，思路是回溯，在递归过程中维护一个“当前已生成的括号串”。判断某个状态是否合法时，可以沿用 20 题的计数思路：右括号数量不能超过左括号数量，左括号数量不能超过 n。这道题用栈也能解，但回溯 + 剪枝更主流，它让你明白括号合法性的另一种表达方式。

第二道是 32. 最长有效括号。这道题难度明显上来了，常见的做法是栈里存索引而不是存字符。栈里先放一个-1作为基准，遇到左括号入栈，遇到右括号弹栈，再用当前索引减去新的栈顶索引，得到目前为止连续有效的长度。为什么不直接存括号字符？因为你需要用索引来计算长度。这就是“栈的语义”变化带来的思维挑战，也是 20 题之后很值得做的一道延伸。

第三道是 678. 有效的括号字符串。它引入了一个通配符*，可以当左括号、右括号或者空字符。经典做法是双栈或者两个计数器：一个栈存左括号位置，一个栈存星号位置，最后统一配对。这个玩法已经远超 20 题基础范围了，但能让你彻底理解“括号匹配”的多种条件。

另外还有 71. 简化路径，也属于括号题之外的“栈模拟”延伸题，本质是用栈来处理路径片段和..回退。刷完 20 题后直接做这道，会有一种熟悉感。

5.2 从“删除相邻重复”出发的同类题目

1047 题也有一个教科书级别的扩展，就是 1209. 删除字符串中的所有相邻重复项 II。区别在于，原始题是删除相邻的两个相同字符，而这道题要求删除相邻的 k 个相同字符。

解法几乎就是把 1047 的思路稍微升级：栈里存的不是单个字符，而是一个包含字符和连续次数的结构。每新来一个字符，如果和栈顶字符相同，就把栈顶的次数加一；当次数达到 k 时，弹出栈顶。如果不同，就压入一个新的节点，次数从 1 开始计。

我给一个简单的 Python 版本：

def removeDuplicates(s: str, k: int) -> str: stack = [] for ch in s: if stack and stack[-1][0] == ch: stack[-1][1] += 1 if stack[-1][1] == k: stack.pop() else: stack.append([ch, 1]) return ''.join(ch * count for ch, count in stack)

这个变形题的识别信号很清晰：从“删相邻两个”变成“删相邻 k 个”，本质上就是要你额外维护一个计数。只要你理解 1047 的“栈顶比较 + 弹出”模式，1209 也只是一层窗户纸。

5.3 栈题的共同识别信号

刷多了以后，我对哪些题适合用栈有了条件反射。描述里如果出现“相邻”“最近”“回退”“成对出现”“闭合顺序”，大概率跟栈有关。现实生活里的例子也很好记：编辑器撤销是栈，浏览器后退按钮是栈，函数调用时的栈帧也是栈。你写递归时，系统编译器就在背后维护一个调用栈。

所以在做题时，如果题目要求你模拟“撤销”或“回滚”行为，先想想能不能用栈表达。这种识别信号比刷题数量的价值更大，因为它能帮你在面对新题时快速定位数据结构方向。

6. 和队列一起看，什么时候该换工具

6.1 队列的经典“排队”场景

虽然今天这两道题都是栈的主场，但训练营标题既然写了“栈与队列”，还是值得把队列一起拉出来看。

队列这种先进先出的结构，适合处理“按顺序、先到先处理”的问题。最常见的算法场景就是 BFS 广度优先搜索：从起点开始，先把第一层邻居入队，再逐层向外扩展，每一层都必须按入队顺序处理，这时候栈就不合适了。类似的还有滑动窗口最大值，那题用的是“单调队列”，在窗口中维护一个有序队列，让队头始终是最大值。

在工程上，消息队列也是队列思想的体现。生产者和消费者解耦，数据先放到队列里，再由消费方按顺序处理。面试系统设计时经常会聊到 kafka、rabbitmq、rocketmq 的选型，核心关注点就在顺序性、可靠性和吞吐量。这跟咱们刷题时学的“先进先出”是一脉相承的，只是落到了分布式系统里。

6.2 栈和队列，怎么快速做选择

我总结了一个简单判断法：新元素需要和谁比较，谁先被处理，决定了用栈还是队列。

• 新元素要和“最近”的元素比较，后到的先触发处理逻辑，用栈；
• 新元素要和“最早”的元素比较，或必须严格按到达顺序处理，用队列。

举几个例子：括号匹配是跟最近的左括号比，用栈；打印任务排队是老的先打，用队列；函数调用返回时，后调用的函数先返回，用栈。这个判断法基本能覆盖九成以上的基础数据结构题。

6.3 一个容易忽略的点：栈题也能嵌套队列思维

栈和队列并非水火不容。有些题表面是栈，实际却要结合别的数据结构。比如最小栈题，要求设计一个栈，能在 O(1) 时间内拿到底部的最小值。经典做法是用两个栈，一个正常存数据，另一个只存“当前出现过的最小值”，每次 push 或 pop 时同步更新。这里底层思想是“单调性维护”，和单调队列有异曲同工之处。

还有一种做法，用一个主栈加一个辅助栈，也属于空间换时间的思路。我提这个是想提醒你，数据结构往往是组合使用的，别做了一道栈题，就只想着栈。等训练营后面接触到单调栈、堆那一类内容时，你会更深刻地感受到，栈只是一个工具，真正值钱的是“你能识别出问题在问什么”。

回到今天这两道题，我觉得最大的价值不是 AC 的瞬间，而是把“最近元素优先处理”这个模型真正建立了。有了这个能力，后面再碰表达式求值、逆波兰表达式、简化路径、接雨水、柱状图中最大的矩形，思路会顺很多。我个人在实际刷题时还有个习惯：每道栈题写完，都手动跑三个特殊例子——空输入、单个字符、全部重复字符。这三个例子能一次性暴露栈空和循环结束后的状态问题，也推荐你试试。