1. 为什么把最小栈、压入弹出序列、层序遍历放到一起刷stack 和 queue 各自的“时间观”1.1 栈和队列的差异一个是叠盘子一个是排队stack 和 queue 刷题时经常被低估因为它们的规则实在简单到一句话就能说清栈是后进先出队列是先进先出。但真做起题来很多人会发现光记住规则远远不够难点不是“懂不懂”而是“用不用得对”。栈的行为可以想象成叠盘子。盘子一个个往上放最后放上去的盘子一定最先被拿走。所以栈天然适合处理“最近的匹配”这类问题比如括号匹配、表达式求值、函数调用栈、浏览器后退。最近发生的事情优先处理这是栈的时间观。队列的行为则是食堂排队。先来的人先打饭后来的站到队尾。所以队列天然适合处理“按顺序推进”的问题比如 BFS、滑动窗口、消息队列、任务调度。先到先服务按到达顺序一层一层往后走这是队列的时间观。这个区别放在算法题里会直接决定你的解题思路。该用栈的时候用了队列或者该用队列的时候用了栈代码写起来都会非常别扭。很多时候不是你算法能力不行而是没有把这两种结构的“时间特性”想清楚。1.2 这三道题刚好覆盖了栈和队列最常见的三种考法最小栈、JZ31 栈的压入弹出序列、102. 二叉树的层序遍历这三道题放在一起价值很大。因为它们正好是三种完全不同的考察角度最小栈考的是“在已有数据结构的功能之上如何附加额外信息”。你需要维护的不只是一个元素的顺序还有每一个时刻的全局最小值。这种题能延伸出一大堆类似问题比如要求同时支持 getMax、要求用两个栈实现队列、要求设计一个支持 O(1) 取中位数的结构等等。栈的压入、弹出序列考的是“用栈去模拟一个确定过程”。题目描述的入栈和出栈是交替发生的你无法预知结果只能老老实实把过程跑一遍。这种模拟题在面试里很常见核心是你能不能把“指针 循环弹出”这套动作写干净不出边界错误。二叉树的层序遍历考的是队列的标准应用。层序遍历要求你按层次从左到右处理节点这种“先来先处理”的节奏正好就是队列的看家本领。理解了这道题BFS 的基本模板就算是彻底掌握后面那些二叉树右视图、锯齿形遍历、N 叉树层序都能直接套。所以说这三道题不是随意堆在一起。它们的共同点是都不需要复杂的高阶算法背什么“双指针”“动态规划”都用不上。它们纯粹考验你是否真的理解了 stack 和 queue 最基本的性质以及你能不能把自己理解到的特性用代码准确表达出来。我甚至可以说这三道题是面试里非常典型的基础盘。基础盘如果写不对后面聊再多的复杂算法都显得虚基础盘写得又快又稳面试官才会相信你是真的会写代码而不是只会背题。2. 最小栈用辅助栈为每一个“栈状态”保存当时的最小值2.1 getMin 的难点O(1) 意味着你不能遍历也不能只存一个变量先看题目描述。155. 最小栈要求你设计一个栈结构支持 push、pop、top、getMin 四个操作并且每一个操作都要在 O(1) 时间内完成。很多第一次接触这道题的人第一反应是把元素存进数组里getMin 的时候遍历一遍找最小值不就行了这个思路功能上确实正确但不满足复杂度要求。每次 getMin 都要扫描全部元素代价是 O(n)。频繁调用 getMin 的话整个结构会退化得很明显。而且面试考这道题本质就是考你有没有能力把 O(n) 的查询优化成 O(1)。那是不是维护一个 int minValue 变量就能解决问题也不是。如果只存一个全局最小值pop 的时候问题马上就出现了假设栈底是 2栈顶是 0当前最小值是 0。当你 pop 掉 0 之后新的最小值应该是 2但你的 minValue 已经回不去了。你不可能知道下一个最小值是什么除非你去遍历剩下的元素。所以这里有一个非常关键的认识最小值不是一个“固定值”而是一个“随栈状态变化的状态量”。栈的每一次 push 和 pop都会产生一个新的状态而每一个状态都需要一个对应的最小值记录。既然状态是按照时间顺序产生的那用来保存这些记录的数据结构也必须是能够回退的。最合适的选择自然就是另一个栈。2.2 辅助栈的同步写法为什么这是最不容易写错的方案辅助栈的写法常见的有两种。第一种是“只在必要时压入辅助栈”。具体规则是入栈时如果新元素小于等于辅助栈栈顶就把新元素也压进辅助栈出栈时如果主栈弹出的元素等于辅助栈栈顶才把辅助栈栈顶也弹出。这样辅助栈里存的就是从小到大的“最小值历史”。第二种是“同步辅助栈”。不管当前元素比最小值大还是小都让辅助栈压入一个“当前状态下的最小值”。也就是说主栈压一个元素辅助栈就压入min(当前元素, 辅助栈之前的最小值)。两个栈的长度始终一样pop 时两个栈一起 popgetMin 只需要看辅助栈的栈顶。我个人在面试和实际写题时更推荐同步写法。原因很简单状态边界最少不需要在 pop 的时候比较两个栈的值也不需要考虑“连续相同最小值”这种容易让人翻车的场景。你甚至可以把主栈和辅助栈想象成两张同步更新的表所有操作都是对齐的逻辑上几乎没有机会出错。C 写法如下class MinStack { stackint st; stackint minSt; public: void push(int x) { st.push(x); if (minSt.empty() || x minSt.top()) { minSt.push(x); } else { minSt.push(minSt.top()); } } void pop() { if (st.empty()) return; st.pop(); minSt.pop(); } int top() { return st.top(); } int getMin() { return minSt.top(); } };注意上面代码里push 时用的是x minSt.top()。为什么是小于等于而不是小于这里就是第一个容易忽略的细节。假设入栈顺序是[1, 1]当前栈里有两个 1。如果你用的是第一个 1 入栈时辅助栈压入 1第二个 1 入栈时因为 1 不小于辅助栈栈顶辅助栈不压入。这时 pop 一次主栈顶是 1辅助栈顶也是 1同时弹出。问题来了主栈里还剩一个 1但辅助栈已经空了getMin 直接访问空栈顶程序崩溃。所以当出现连续重复最小值的时候辅助栈里必须为“每一个”最小值都保留记录。用就能保证这一点。2.3 少用空间的差值法面试能讲但实现要小心有些面试官会追问“你能不能用 O(1) 的额外空间实现最小栈”。这个追问确实有解思路很巧妙栈里不存真实值而是存真实值和当前最小值的差值。具体地说用diff x - currentMin作为入栈元素再用一个变量currentMin来维护当前最小值。入栈时如果栈为空令currentMin x压入 0。否则计算diff x - currentMin并压入。如果diff 0说明新元素比当前最小值还小更新currentMin x。出栈时取出栈顶diff。如果diff 0说明正在弹出一个“曾经的最小值”那么前一个状态的最小值恢复为currentMin - diff。否则当前最小值不变。顶元素的计算则是如果diff 0真实值是currentMin diff。如果diff 0说明当前最小值就是栈顶元素真实值就是currentMin。这个方案空间确实是 O(1)只用了一个额外变量。但它有两个明显的坑第一个坑是溢出。diff x - currentMin完全有可能是负数也可能差得非常大。用 int 保存遇到极端数据可能溢出所以 C 里要用 long longJava 里要用 longPython 倒是不怕这种整数溢出。第二个坑是代码可读性。你维护的是一个被隐藏的“真实值语义”top 和 getMin 都要做额外的判断和运算写起来容易懵出 bug 之后也不太好排查。所以我的建议是如果只是为了通过题目和面试用同步辅助栈就足够了。差值法可以当作一个“我知道还有这种解法”的知识点来准备不一定非要在正式写代码时采用。直接给一个 C 差值法版本方便你对照理解class MinStack { stacklong long s; long long curMin 0; public: void push(int x) { if (s.empty()) { curMin x; s.push(0LL); } else { long long diff (long long)x - curMin; s.push(diff); if (diff 0) curMin x; } } void pop() { long long diff s.top(); s.pop(); if (diff 0) { curMin curMin - diff; } } int top() { long long diff s.top(); if (diff 0) return (int)(curMin diff); return (int)curMin; } int getMin() { return (int)curMin; } };我刚写出来时也经常在 top 方法里绕晕。后来总结了一个记忆点凡是入栈时的diff 0说明栈顶元素自己就是那个新的最小值所以 top 直接返回 curMin如果diff 0说明栈顶元素是“普通值”它在当前时刻的真实值是“当前最小值 差值”。2.4 面试追问往往会从这里展开最小栈这道题面试官不会只满足于“你写对了”他大概率会追问几个方向能不能同时得到最大值可以再维护一个辅助栈规则完全对称或者直接在主栈里存一个pairint,int / Node{val, minVal, maxVal}。能不能用两个栈模拟队列这也是 JS 面试里非常常见的题思路是用两个栈做“倒腾”不过那是另一个话题。能不能在 pop 时返回真实值很多语言的栈 pop 不一定返回元素可以在 pop 之前先调用 top。这些追问的本质是在测试你对栈结构“状态可回退”这个特性的理解是否深入。你只要理解到“辅助栈保存的是每个时刻的附加状态”追问基本都答得出来。3. 栈的压入、弹出序列用一个栈去“重放”整个出入过程3.1 题意翻译入栈顺序已知问出栈顺序能不能实现JZ31 这道题通常的描述是输入两个整数序列第一个序列表示栈的压入顺序第二个序列表示该栈的弹出顺序判断第二个序列是否可能是该栈的弹出序列。先确认一个前提压入顺序不是说让你一口气把所有元素全部 push 进去然后再一口气全部 pop 出来。压入和弹出是可以交替进行的。例如压入顺序是[1,2,3,4,5]你可以先压入 1、2弹出 2再压入 3再弹出 3以此类推。题目问的就是在这种自由交替的操作下是否存在一种操作序列最终得到给定的出栈顺序。举个例子。入栈序列[1,2,3,4,5]出栈序列[4,5,3,2,1]是合法的。过程可以这样走压入 1、2、3、4弹出 4压入 5弹出 5再依次弹出 3、2、1。而出栈序列[4,3,5,1,2]则不合法。因为要先把 1 弹出来时栈顶是 21 被压在下面除非先弹出 2但那样出栈顺序又对不上。所以结论是 false。这类题不需要你去枚举所有可能的出栈序列。一个序列能否成为某个入栈顺序的出栈序列核心判定方式就是用栈把过程重新“跑”一遍看能不能跑通。3.2 模拟算法一个栈 一个指针模拟的思路非常直白用一个真实栈 st 来模拟入栈过程。用一个指针 j 指向 popV 中下一个待匹配的位置。遍历 pushV把每个元素依次压入 st。每次压入后检查栈顶是否等于 popV[j]。如果相等就弹出栈顶并把 j 后移。注意弹出之后栈顶可能又等于新的 popV[j]所以要用 while 循环反复检查直到栈顶不匹配或者栈空为止。全部 pushV 处理完之后如果栈是空的说明所有元素都按 popV 的顺序弹出了返回 true否则返回 false。C 代码如下bool IsPopOrder(vectorint pushV, vectorint popV) { if (pushV.size() ! popV.size()) return false; stackint st; int j 0; for (int x : pushV) { st.push(x); while (!st.empty() st.top() popV[j]) { st.pop(); j; } } return st.empty(); }这里有个很容易踩的细节while循环里判断的是popV[j]而不是popV[i]。因为i遍历的是压入顺序j才是在弹出顺序中的进度。很多第一次写的人会把这两个下标弄混导致程序行为完全不对。另一个容易被忽略的点是为什么用while而不是if因为一个元素被弹出后很可能下一个栈顶仍然正好是下一个要弹出的元素。例如入栈序列[1,2,3]弹出序列[3,2,1]。当你处理到 3 时栈里是[1,2,3]第一次 while 判断发现栈顶 3 等于 popV[0] 弹掉 3j 变成 1这时栈顶变成 2又一次 while 判断又等于 popV[1]再弹。如果只写一个if就只能弹掉 3剩下的 2 和 1 就会卡在栈里最后误判为 false。3.3 边界情况空序列、单元素、全逆序、全正序这类模拟题想拿满分边界情况必须自己先过一遍。如果 pushV 和 popV 都为空根据题目约定一般算作合法。上面代码里两个 vector 长度相等且都是空for 循环不执行最后 st.empty() 为 true返回 true。如果只有一个元素比如 pushV 为[1]popV 为[1]那么压入 1 之后while 判断栈顶 1 等于 popV[0]弹掉j 变成 1循环结束栈空返回 true。如果 popV 是 pushV 的完全逆序比如 pushV 是[1,2,3,4,5]popV 是[5,4,3,2,1]那么你需要先把所有元素全部压入栈底最后依次弹出。模拟过程中栈最多会累积 5 个元素每次 while 判断都只能弹出一个匹配的栈顶最后栈空返回 true。如果 popV 和 pushV 完全一致比如[1,2,3,4,5]对应[1,2,3,4,5]那么每次压入一个元素后while 循环会立刻把它弹掉栈始终只有 1 到 2 个元素模拟起来非常轻松。如果 popV 长度和 pushV 长度不一致应该直接返回 false这是题目没有明说但很合理的防御性判断。保持这样的习惯在面试中也会给面试官留下“考虑问题全面”的印象。另外提一下重复元素。如果 pushV 里有重复数字比如[1,1,2]模拟逻辑依然是安全的。因为我们是按照“值是否相等”来比较而 pushV 的顺序已经固定重复数字所在的先后位置不会混淆。理论上如果出现两个相同数字你可能需要区分“弹出的是哪一个 1”但在栈模拟里只要值匹配弹出的必然是当前栈顶的那个所以结果依然唯一不需要额外处理。3.4 为什么“能弹就弹”是对的唯一性论证这道题写代码不难难的是向面试官解释“为什么弹出时要立刻弹出而不是先留着看看”。我一般在面试里会这样解释当前栈顶正好等于 popV[j] 时如果不弹出这个元素就会被后续压入的元素盖在下面。而后续元素一旦压入栈顶就变了popV[j] 这个元素距离栈顶只会越来越远。你想在后续某个时刻把它弹出来就必须先把压在上面的一堆元素弹出来但这又会破坏 popV 的顺序。换句话说当前不弹只会让后面的匹配变得更加不可能。所以“能弹就弹”不是一个凭直觉的贪心策略而是唯一可行的策略。因为入栈顺序是固定的你不能跳过任何一个 pushV 元素出栈顺序也是固定的你必须按 popV[j] 的顺序弹出。整个模拟过程其实没有任何自由选择的余地匹配就弹不匹配就继续压入。这就是为什么我们可以直接用一个栈去“重放”整个过程而不需要回溯或判断多种可能性。4. 二叉树的层序遍历queue 的 BFS 就是为这种场景设计的4.1 为什么用 queue 而不是 stack层序天然是先进先出二叉树的层序遍历要求返回一个二维数组第一层节点放在第一个数组里第二层节点放在第二个数组里每一层内部从左到右排列。你可以想一想如果用一个栈去实现层序遍历会是什么效果。栈是后进先出当你把根节点的左右孩子压入栈后下一次弹出的会是右孩子而不是左孩子这样同一层的访问顺序就颠倒了。如果你继续用栈硬做就需要额外记录节点所在的层数最后再对每层单独排序调整绕了很大的弯子而且代码可读性极差。队列则完全匹配这个场景。队列是先进先出我们把根节点入队然后从队头取出节点再把它的左右孩子依次入队。这样下一层的节点会排在当前层剩余节点之后严格按照从左到右的顺序被处理。层序遍历的过程本质上就是“先到达先处理”也就是 BFS 的核心思想。所以这道题的第一原则就是见到“层序”两个字优先想 queue。4.2 标准 BFS 模板先记录当前层大小再一次性处理本层层序遍历的标准写法核心是“每一轮处理一层”。很多人在第一次写时都会犯同一个错误以为只要while (!q.empty())不断弹出然后把左右孩子入队就可以了。但这样做有一个问题队列里会同时混入当前层的剩余节点和下一层的节点你不知道哪里是层的边界。解决办法很简单每一轮循环开始前先记录一下int size q.size()这个 size 就是当前层节点数量。然后用一个 for 循环处理 size 个节点每弹出一个节点就把它的左右孩子入队。这样处理完 size 个节点后正好当前层全部弹出队列里剩下的全部都是下一层节点。C 代码如下vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (root nullptr) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; }这里最容易犯错的地方是不要在 for 循环的条件里写i q.size()。因为在循环内部q 的 size 会随着孩子节点的入队而变大你本来只想处理 size 个节点结果会处理掉比 size 更多的节点把下一层的节点也提前混进当前层。很多机考面试的 WA根源就在这么一行小小的条件判断上。另一个常见错误是忘记判空。root 为空时直接返回空数组不能访问root-val否则运行时会崩。这个习惯要养成几乎所有二叉树的题都需要先处理空根。4.3 一堆变体锯齿形、自底向上、右视图、N 叉树层序遍历模板写熟了很多同类型的题就是改一行。自底向上层序遍历先按正常的 BFS 得到从上到下的结果最后把整个 res 反转一次。时间复杂度和空间复杂度都不变只是在最后多一个 reverse。锯齿形层序遍历之字形第一层从左到右第二层从右到左第三层再从左到右。最简单的做法是先正常 BFS 得到每一层的顺序然后在处理结果时把偶数层下标为 1 的层、下标为 3 的层反转即可。当然也可以用双端队列实现但直接反转更容易理解也不容易出现边界问题。二叉树右视图只返回每层最后一个节点。BFS 时把每一层的最后一个元素收集起来就行。判断条件通常是i size - 1时记录逻辑非常直观。N 叉树层序遍历把if (node-left)和if (node-right)两行换成对node-children的遍历循环其余模板完全一致。每层最大值、每层平均值也都是在这个模板上追加一个统计逻辑。所以建议是把标准模板一次性写熟然后针对每个变体去理解“它到底改变的是哪一行”而不是每次都重新推演 BFS 过程。4.4 复杂度与极端情况空间不是 O(1)层序遍历的时间复杂度是 O(n)因为每个节点都会被访问恰好一次。空间复杂度不是 O(1)在最坏情况下队列中可能同时保存一整层的节点。对于一棵满二叉树最后一层大约有 n/2 个节点所以空间复杂度是 O(n)。有些追求极致的面试官还会问能不能用递归的 DFS 写这道题答案是可以。你可以深度优先遍历同时记录当前深度 depth然后把节点值放到res[depth]这个数组里。因为深度优先从左子树开始所以同一层内的自然也就是从左到右。但这样做的问题是不够直观而且要保证 res 的每一层数组先创建好否则会越界。从面试的角度如果题目明说层序遍历最优的表达思路还是用队列 BFS。另外值得提醒的是不要在小数据量时轻视空指针判断。LeetCode 和牛客上很多二叉树题目的 root 都可能为空不判空直接崩溃。判空放在函数入口第一行是成本最低但收益最高的防御性代码。5. 三道题连起来看调试顺序、代码习惯和面试表达5.1 最容易出 bug 的五个细节逐个对号入座把三道题放在一起复盘你会发现它们各自的易错点其实非常集中。只要在提交前检查一遍下面这五个点基本就能避免大部分 WA 和 RE。最小栈辅助栈是否和主栈同步 pop。同步写法不用判断直接把两个栈一起 pop 就行非同步写法容易漏掉辅助栈的 pop导致 getMin 访问到已过期的最小值。辅助栈 push 时用而不是。连续重复最小值时使用会丢记录。压入弹出序列比较值时用的是 popV 的下标 j不是 pushV 的下标 i。弹出循环必须用while而不能只写一次if。每轮都先判断栈非空再访问栈顶避免空栈异常。层序遍历每轮循环开头先用int size q.size()固定本层节点数后续 for 循环条件用这个 size不用动态变化的q.size()。函数入口先处理root nullptr的情况。这些都是非常小的点但你在现场写代码时越紧张越容易在细节上翻车。我自己刷题的体会是不要指望“想清楚再写”就能避开所有细节很多错误是写完代码之后用测试用例跑一遍才暴露出来的。所以一定要在提交之前自己构造几个边界用例来验证。5.2 动手写代码前先在草稿纸上画出状态变化这三道题有一个共同特点都是“状态变化”导向的模拟题。最小栈里有两个栈压入弹出序列里有一个栈和两个数组下标层序遍历里有一个队列和一个正在处理的层。它们的状态变化过程用文字叙述一堆都不如画一个简单的表格直观。例如最小栈你在草稿纸上画两列左边是主栈内容右边是辅助栈内容。当主栈 push 一个元素辅助栈同步 push 一个元素两个栈高度保持一致。你只要画两三次就会理解为什么同步写法天然不会错。压入弹出序列也是。你写上 pushV 序列画一个向右的指针 j 指向 popV 的当前元素然后模拟入栈一个元素画栈里的元素堆叠情况。每弹出一个就把 j 往后挪一格。整个过程画一遍之后代码里的 while 循环条件就非常清楚了。层序遍历同样可以用队列状态图来推演。每一轮 while 循环开始时的size就是当前层的节点数画的时候可以给队列里的节点标上层号你会看到处理完一层之后队列里恰好就是下一层节点。这个“画图推演”的习惯比直接硬写代码要可靠得多。我见过不少同学代码能力强但每到面试写模拟题就会卡住。主要原因不是不会而是没有耐心先把过程捋顺。真正有效的做法是先花一分钟画状态图再花三分钟写代码而不是一上来就敲键盘。5.3 面试时怎么讲思路才能显得“你是真懂”最后聊一点面试表达的技巧。这三种题的代码都不算长但面试官真正想听到的不是你背下来的代码而是你对题目本质的判断。最小栈你可以这样说“这道题的关键在于 getMin 要求 O(1)单纯用一个最小变量无法在 pop 之后恢复上一个最小值所以我用辅助栈记录每个历史状态的最小值两个栈同步更新。”这样一开口面试官就知道你对“维护状态”这件事有概念。压入弹出序列你可以说“我用一个栈模拟整个入栈和弹栈过程遍历 pushV把元素逐个压进去。只要栈顶等于 popV 当前要弹出的元素就立刻弹出。因为此时如果不弹后面压入的元素会把这个元素盖住它就更不可能按顺序弹出来。”最后这句“因为此时如果不弹”很重要它不是套路话而是向面试官证明你理解了这个模拟过程的唯一性。层序遍历你可以说“层序天然是先进先出所以我用队列做 BFS。每轮开始先记录当前队列长度然后一次性处理当前层所有节点这样自然就把每一层切开了。”面试官听到“先记录队列长度来切层”就会知道你是真正写过这道题而不是只会死记硬背模板。我个人在实际刷题和准备别人面试时的感受是这三道题并不难但它们是很好的“照妖镜”。如果你能一次性把代码写得干净、边界想得周全、思路表达得清楚那么栈和队列这一块的绝大多数问题基本都难不住你了。反过来如果这三道题反复出 bug那说明你在“数据结构执行过程”的想象上还需要多下功夫。把草稿纸用起来把状态图一张一张画扎实比多做十道新题更管用。