企业官网建设流程全解析

栈和队列这两兄弟，在很多人眼里只是课本上的一个概念：一个是后进先出，一个是先进先出，背完定义就完事了。但真到了刷题的时候你会发现，它们的作用远不止于此。就拿《代码随想录》Day 11 这三道题来说——150. 逆波兰表达式求值、239. 滑动窗口最大值、347. 前 K 个高频元素——一道把“栈”用在表达式求值上，一道用“单调队列”解决滑动窗口的极值问题，一道用“堆”来维护 TopK。三题做完，你对“栈和队列的变种”基本就有感觉了。

这篇文章我会按刷题笔记的方式，把每道题的思路、代码、边界坑都讲一遍，也会说说为什么这个解法能过、那个解法会超时。适合正在准备面试、或者刚学到栈与队列想加深理解的同学。如果你已经能独立 AC 这三道题，可以跳到最后的“坑位复盘”部分，有些细节估计你也中过招。

1. 三道题放在一起，到底在考什么

1.1 从“后进先出”到“队列的变种”

栈和队列在教科书里的定义都很简单：栈是后进先出，队列是先进先出。但真实工程和算法题里，我们几乎不会只用“最朴素”的栈和队列。函数调用栈回收、浏览器前进后退、编译器表达式求值、线程池的阻塞队列、业务系统里的消息队列……这些场景都在用栈和队列的变种。

Day 11 这三道题特别典型的地方在于：它们没有一道是直接让你“用栈模拟括号匹配”或者“用队列模拟排队”，而是把数据结构嵌到了具体的计算场景里。逆波兰表达式要求你在无括号的情况下完成表达式求值，本质是“后进先出”在计算顺序上的体现；滑动窗口最大值要求你在窗口不断移动时快速取极值，本质是“先进先出”加“单调性约束”；前 K 个高频元素则更进一步，队列不再按先进先出排队，而是按“优先级”排队，这就是堆（优先队列）的雏形。

所以我的建议是把这三道题当作一条学习链路：先用最原始的栈解决计算问题，再把队列升级成“双端”和“单调”，最后把队列升级成“按权值排序的优先级队列”。一条链学下来，你对数据结构“为什么需要这些变形”会有非常直观的理解。

1.2 每道题对应的知识点定位

先给一个全局对照表，方便你回顾时快速找到重点。

三道题对应三种抽象层级：栈是“后进先出”的直接应用；双端队列允许同时操作头和尾，开阔了设计空间；堆则是对“队列”的一种彻底重构——谁优先级高谁先出。真正吃透它们，比死记“栈适合做括号匹配、队列适合做 BFS”这种模板要更有收获。

2. 150 题：逆波兰表达式求值

2.1 后缀表达式为什么这么“方便”

逆波兰表达式也叫后缀表达式，核心特点是运算符放在两个操作数后面，比如"2", "1", "+", "3", "*"对应我们平时写的中缀表达式(2 + 1) * 3。人类习惯中缀，是因为有运算符优先级和括号；但计算机处理中缀非常痛苦，需要反复扫描、比较优先级。而后缀表达式只有一个规则：从左往右扫，遇到数字就压栈，遇到运算符就把栈顶两个数字弹出做运算，结果再压回去。全程不需要判断优先级，也不需要括号。

这就像你手工算(2 + 1) * 3时，正常人不会先去算2 + 1再去乘 3 吗？其实只是人脑天然带优先级判断。编译器为了统一处理，会把中缀转成后缀，然后交给一个简单的栈机器去执行。很多面试官也会追着问“中缀怎么转后缀”，其实就是扫一遍表达式，用栈临时保存运算符，等括号或优先级触发时再弹出。

2.2 求值流程与代码实现

这道题的输入tokens是一个字符串数组，里面既有数字也有+ - * /四种运算符。用一个栈就能完成全部操作，流程很简单：

1. 遇到字符串形式的数字，转成Number后压栈。
2. 遇到运算符，弹出栈顶两个元素，a是后弹出的那个，b是先弹出的那个。
3. 计算a 运算符 b，把结果压回栈。
4. 全部处理完后，栈里唯一的元素就是答案。

JS 实现如下：

function evalRPN(tokens) { const stack = []; const ops = new Set(['+', '-', '*', '/']); for (const token of tokens) { if (!ops.has(token)) { stack.push(Number(token)); continue; } const b = stack.pop(); const a = stack.pop(); let result; switch (token) { case '+': result = a + b; break; case '-': result = a - b; break; case '*': result = a * b; break; case '/': result = Math.trunc(a / b); break; } stack.push(result); } return stack.pop(); }

这里最容易被忽略的就是减法和除法中a和b的顺序。因为栈是后进先出，2 1 -的意思是2 - 1，不是1 - 2。第一次写这道题十有八九会把a + b写成b + a，加法和乘法无伤大雅，但减法和除法会直接导致答案错误。

2.3 除法取整和边界处理

这个题在 C++ 或 Java 里，整型除法本来就是向零取整，直接a / b就行。但在 JavaScript 里，a / b得到的是浮点数，比如-3 / 2是-1.5。题目要求结果向零截断，也就是-1，所以必须用Math.trunc(a / b)。

还有一个隐藏坑：parseInt看起来也能实现“截断”，但它对负数的处理方式并不理想。比如parseInt(-1.5)会先被转成字符串"-1.5"，再解析出整数-1，结果恰好一样；但parseInt(0.0000001)这类场景会有意外，Math.trunc才是真正的“向零取整”，语义更干净。所以刷题时我建议统一用Math.trunc。

时间复杂度是 O(n)，因为每个 token 最多进出栈一次。空间复杂度也是 O(n)，极端情况下表达式全是数字。题目约束说表达式一定是合法的，所以不用判空，但如果你要扩展成“计算器”功能，合法性和除零检查都不能少。顺便说一句，这个题做对了，后面做“基本计算器”系列会轻松不少，因为核心的“栈机器”你已经搭过一遍了。

3. 239 题：滑动窗口最大值

3.1 暴力解法的问题在哪里

这道题描述很直白：给一个数组nums和一个窗口大小k，窗口每次往右移一格，返回每个窗口里的最大值。最朴素的想法是两层循环，外层遍历所有窗口，内层扫一遍当前k个元素找最大值，时间复杂度是 O(nk)。数据量小没事，但 LeetCode 的测试数据直接把长度拉到10^5左右，O(nk) 直接超时。

有人可能说：那我用一个大顶堆不就行了？窗口移动时，往堆里塞新元素、弹出旧元素，堆顶就是最大值。思路对了一部分，但问题在于堆本身不支持“按值删除任意元素”——你得知道旧元素的下标，并且在堆里精确删除，这会让堆的调整逻辑变得非常复杂，时间复杂度也会退化。所以这道题的标准解法不是“优先队列”，而是一个很巧妙的数据结构：单调队列。

单调队列本质上仍然是双端队列，但它在入队时做了一件关键的事情：把没资格当队头的元素提前弹掉。这样队列里的元素从队头到队尾保持“单调递减”或“单调不减”，队头永远是当前窗口的最大值。

3.2 单调队列的两个动作：去尾和去头

我刷这道题的时候，最直观的感觉就是“窗口里留着那些较小的数字没有意义”。举例：窗口[3, 1, 2]，最大值是 3，那 1 和 2 暂时有没用？当窗口往后移，3 离开窗口后，2 有可能成为新窗口最大值；但 1 除非前面所有元素都走了，否则永远不可能排在 2 前面成为更大值。也就是说，只要后面存在更大的数，前面较小的数就可以被淘汰。

这就是“去尾”动作：每次新元素进队前，从队尾开始弹出所有比它小的元素。这样维护出来的队列，从队头到队尾一定是递减的，队头就是当前窗口最大值。然后是“去头”动作：窗口滑动时，要判断队头元素是否已经滑出窗口。如果滑出了，就从队头弹出。

这两个动作一前一后，配合得天衣无缝。生活类比就是：一个班级的队列，如果有新同学个子更高，那么排在他前面的所有“矮个子”都不用再管了；但如果队列最前面的同学已经毕业离校，就要把队头清掉。代码里最核心的思路就是把“比新元素小的旧元素”在入队时提前干掉，避免窗口滑动后还要重重比较。

3.3 代码实现与复杂度分析

我统一用“存下标”的方式实现，因为存下标才能准确判断元素是否过期。如果只存值，窗口滑到一半你根本不知道这个值还在不在窗口里，这是很多初学者最容易掉进去的坑。

function maxSlidingWindow(nums, k) { const queue = []; // 双端队列，存放元素下标，对应的值从大到小 const result = []; for (let i = 0; i < nums.length; i++) { // 去头：队头已经滑出窗口 while (queue.length && queue[0] <= i - k) { queue.shift(); } // 去尾：所有比当前元素小的元素都没有存在价值 while (queue.length && nums[queue[queue.length - 1]] < nums[i]) { queue.pop(); } // 当前元素入队 queue.push(i); // 窗口形成后，每次移动都记录队头对应的值 if (i >= k - 1) { result.push(nums[queue[0]]); } } return result; }

注意去尾的判断条件是<还是<=。如果数组里有重复值，比如[5, 5, 3]，用<会把旧的 5 留在队尾，但旧 5 的贡献其实已经被新 5 覆盖，区别不大；用<=会让新元素把旧元素弹掉，代码更简洁，也不影响正确性。实际面试时我习惯写<，因为在解释“相等时为什么保留旧元素”时理由更充分——旧元素会在更早的时间过期，如果它的值和新元素相同，保留它会更快被淘汰，不会影响正确性。

每个元素最多入队一次、出队一次，所以整体复杂度是 O(n)，空间复杂度 O(k)。这个“去尾”操作可能会让你觉得内层 while 是 O(n) 的，但仔细想想，每个元素只会被 pop 一次，均摊下来就是 O(1)。这也是单调队列最经典的地方：用均摊代价换来了每个窗口最大值 O(1) 的查询。

4. 347 题：前 K 个高频元素

4.1 先统计频率，再考虑怎么选出前 K

这道题的要求是返回数组中出现频率最高的 K 个元素。第一步没有悬念：先扫一遍数组，用哈希表统计每个数的频率，复杂度 O(n)。难点在第二步：怎么从一堆频率里找出最大的 K 个。

最简单的办法是把所有(元素, 频率)按频率排序，然后取前 K 个，时间复杂度 O(n log n)。这在数据量小的时候没问题，但 LeetCode 测试数据一大，O(n log n) 就有风险，而且面试官大概率会追问一句“能不能更快”。标准答案是维护一个大小为 K 的小顶堆，堆里只放“当前频率最高的 K 个元素”。每来一个新元素，如果它比堆顶元素（当前第 K 大）频率还高，就把堆顶弹掉，把它塞进去。这样遍历完所有频率后，堆里留下的就是前 K 个高频元素。

这里有一个特别反直觉的选择：为什么不用大顶堆？大顶堆每次弹出的都是最大值，那最后堆里留下的反而是“频率最低的那批”，方向完全反了。小顶堆的堆顶是整个堆里最小的高频元素，但它恰好是“进入 TopK 的门槛”——新元素只有跨过这个门槛才有资格入堆。这就是“筛选”和“排序”的区别：大顶堆适合求最小值，小顶堆适合求最大值。

4.2 手写一个小顶堆，而不是调现成的库

第二道题我们用了双端队列，这道题的重点是优先级队列。Java 和 C++ 的面试者可以直接用PriorityQueue或priority_queue，但用 JavaScript 刷题就得手写堆了。手写堆其实不复杂，关键在于吃透两个操作：向上调整（上浮）和向下调整（下沉）。我用一个最小堆来存[元素, 频率]，比较时只看频率。

class MinHeap { constructor() { this.heap = []; } size() { return this.heap.length; } peek() { return this.heap[0]; } push(item) { this.heap.push(item); this._bubbleUp(this.heap.length - 1); } pop() { if (this.size() === 1) return this.heap.pop(); const top = this.heap[0]; this.heap[0] = this.heap.pop(); this._bubbleDown(0); return top; } _bubbleUp(index) { while (index > 0) { const parent = Math.floor((index - 1) / 2); // 比较频率：当前节点小于父节点，就交换 if (this.heap[parent][1] <= this.heap[index][1]) break; [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]]; index = parent; } } _bubbleDown(index) { const n = this.size(); while (true) { const left = index * 2 + 1; const right = index * 2 + 2; let smallest = index; if (left < n && this.heap[left][1] < this.heap[smallest][1]) { smallest = left; } if (right < n && this.heap[right][1] < this.heap[smallest][1]) { smallest = right; } if (smallest === index) break; [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]]; index = smallest; } } }

然后主函数就很简单：

function topKFrequent(nums, k) { const freq = new Map(); for (const num of nums) { freq.set(num, (freq.get(num) || 0) + 1); } const heap = new MinHeap(); for (const [num, count] of freq.entries()) { heap.push([num, count]); if (heap.size() > k) { heap.pop(); } } return heap.heap.map(item => item[0]).reverse(); }

为什么最后要reverse()？因为堆结构并不保证数组完全有序，但堆顶是当前最小频率元素，而我们要返回“前 K 个高频元素”，顺序在 LeetCode 里通常不重要。如果希望返回数组里越靠前频率越高，可以先把数组按照频率排一下，也可以直接从堆里逐个pop()，弹出的顺序是频率从小到大，再reverse一下就是从大到小。上面的.map(...).reverse()实际上取的是heap.heap数组的原始顺序，不保证频率严格递减，但结果一定是合法 TopK。

4.3 时间复杂度分析和桶排序的加分思路

小顶堆做 TopK 的时间复杂度是 O(n log k)，其中 n 是原数组长度，k 是堆的大小。因为堆中始终只保留 K 个元素，每次插入和删除都是 O(log k)。如果 K 远小于 n，这个优势非常明显。如果 K 接近 n，那直接用全排序反而省事，所以面试时可以主动讨论“K 的大小对方案选择的影响”，这会让面试官觉得你不是在背模板。

如果还想进一步优化，可以聊聊“桶排序”变体：既然频率的取值天然落在[0, n]区间内，可以开一个长度为n + 1的数组，把相同频率的元素放在同一个桶里，然后从高频率桶往低频率桶遍历，收集满 K 个就停。时间复杂度是 O(n) 的，但因为需要额外维护“频率 → 元素列表”的映射，空间开销更大。这个思路在“求出现次数最多的元素”这类题里非常通用，笔试写出来是加分项。

不过我的建议是：先稳稳写出小顶堆版本，再口头补充桶排序思路。不要一上来就写桶排序，万一频率映射处理不好，反而容易出 bug。

5. 坑位复盘与实战建议

5.1 三道题里我踩过、也见过别人踩的坑

刷题刷多了你会发现，真正让人卡住的往往不是“没思路”，而是“边界细节”。我把三道题里最容易踩的坑整理成一个速查表，建议收藏，下次二刷前先扫一眼。

还有一个非常容易忽略的坑：150 题里的tokens是字符串数组，"3"是字符串，"+"也是字符串。判断一个 token 是不是数字，不要用typeof token === 'number'，而要看它是不是运算符。我在第一次实现时用isNaN(token)判断，结果把"-11"这种负数也当成了数字，其实误打误撞还算顺利，但这种“隐式转换”容易埋雷，不如直接维护一个运算符集合，判断逻辑更清晰。

5.2 从这三道题延伸到工程和面试

栈和队列的题目范围其实很广。150 题的思路可以延伸到“基本计算器”“表达式求值”“编译原理里的语法分析”；239 题的单调队列则是“滑动窗口极值”这一类题目的核心武器，后面做“最长重复字符替换”“最大连续 1 的个数”都能用上类似的双指针加窗口思想；347 题更是面试高频，因为 TopK 问题在各行各业都会出现，比如推荐系统的热门物品、搜索引擎的热搜词、日志系统里的错误统计排名。

另外我想多说一句工程方面的联想：一说到“队列”，不少人会想到“消息队列”“阻塞队列”“线程池的阻塞队列”，这些确实是分布式系统和并发编程里的重要概念。但算法题里的队列更“底层”，它是一种结构约束；消息队列则是生产者消费者模型下的“数据管道”，两者并不是一回事。理解了算法里的队列和优先队列，再去看“阻塞队列的实现”“DelayedQueue 延迟队列”这些工程概念时，你会比只背八股文的人快很多，因为你知道底层原理是环形数组、链表还是堆。

5.3 刷题节奏的建议

Day 11 能做到这里，说明前面的数组、链表、哈希表应该都练得差不多了。这三道题放到这个阶段很有讲究：150 题考察基础编码规范，239 题考察数据结构变形能力，347 题考察综合设计能力。我的建议是：

第一遍先自己做，哪怕超时也没关系，重要的是能写出一个“能跑”的版本。第二遍再对照正确思路优化。第三遍可以尝试在纸上画出单调队列的入队出队过程，能把每一步数组状态写出来，这个知识点基本就焊死在脑子里了。如果时间紧，至少把 239 和 347 的思路复述一遍，因为你不知道面试官会不会突然追问“滑动窗口最大值有没有 O(n) 解法”。

我个人的经验是：刷题不要一味追求数量，这三道题只要做透，比囫囵吞枣刷十道题都值。尤其是 239 的单调队列，初见可能觉得“这个思路好妙”，但你如果能自己推导出“去尾”这一步背后的淘汰逻辑，以后再遇到类似问题就不是背诵，而是真正的算法思维了。