企业官网建设流程全解析

代码随想录刷题打卡来到 Day10，栈与队列专题安排了三道硬菜：150 逆波兰表达式求值、239 滑动窗口最大值、347 前 K 个高频元素，外加一个阶段性总结。这三道题几乎把栈和队列最核心的应用场景串起来了——"最近相关性"用栈、"窗口极值"用单调队列、"频率 TopK"用小顶堆或桶排序。不管是准备大厂算法面试，还是想扎扎实实补一遍数据结构底子，这几个模式都值得反复嚼。

我从大一接触栈和队列时只会背"先进后出、先进先出"，到现在能像条件反射一样在题目里识别出该用哪种队列形态，中间踩过不少坑。这篇记录我尽量把每一步都讲透，包括为什么用这种数据结构、边界条件在哪里、代码为什么这么写，最后再聊聊刷完这三题后对"线性结构"的认知升级。适合正在刷题但还没完全吃透单调队列和 TopK 思路的朋友，也适合面试前需要一个快速回顾手册的人。

1. 整体思路：三道题背后的数据结构思维

1.1 栈：解决"最近相关性"的天然工具

先聊 150 逆波兰表达式求值。很多人第一次看到逆波兰表达式会懵，感觉一堆操作符和数字混在一起，不知道从哪里下手。但你只要抓住一个关键点：后缀表达式已经把运算符优先级和括号全部消掉了，每个运算符真正需要的两个操作数，就是它左侧最近的两个数。这种"最近相关性"，正是栈最擅长的场景。

栈的本质是"后进先出"，它只允许操作栈顶。如果一个运算需要倒序处理历史数据，或者只需要关心最近几个状态，那用栈就不用考虑中间那些已经被处理完的元素。逆波兰求值时，遇到数字就压栈，遇到运算符就弹出最近的两个数字，算完再压回去。这个过程等价于把表达式从左到右扫描一遍，栈中始终保存着"当前还没有被消费的中间结果"。

顺带一提，热词里总能看到"栈帧形成过程""backtrace 栈回溯""ARM 调用栈回溯"这些概念。函数调用栈其实就是栈在系统层的真实写照：每次函数调用会压入一个栈帧，函数返回时弹出栈帧，所以栈帧的空间和局部变量数量密切相关。C 语言里常说"局部变量越少，所占栈空间越小"，本质就是因为局部变量放在当前栈帧中，栈帧的大小直接受局部变量影响。理解了这个场景，再看算法题里的"stack.pop()"，你会更有画面感。

1.2 队列的"变形金刚"：单调队列与优先队列

239 滑动窗口最大值考的是队列，但它不是直接用普通队列。普通队列解决的是"先进先出"的公平缓冲问题，而滑动窗口需要的是"随时知道窗口内最大元素"以及"过期元素能被及时移除"。

这里用到了双端队列（deque），并在其基础上维护单调性，也就是常说的单调队列。单调队列的队首始终是窗口的最大值，队尾负责淘汰那些"永远不会再成为最大值"的旧元素。它和普通队列最大的区别是：普通队列只从队首出队、队尾入队；单调队列允许在队尾直接把不合格的元素"顶掉"。

同样出现在这组题里的 347 前 K 个高频元素，则需要优先队列（堆）。优先队列的逻辑是"每次出队的是优先级最高或最低的元素"，对应到 "TopK" 问题，小顶堆记住当前最大的 K 个值，堆顶就是这 K 个里最小的那个，新来一个更大的就替换掉堆顶。你看，同样是"队列"，但根据需求衍生出了完全不同的形态：单调队列、优先队列，生产环境里还有阻塞队列、延迟队列、消息队列。理解这些变体的本质，比单纯背 API 有用得多。

1.3 三题背后的复杂度对比

这三道题放在一起，刚好构成了一组清晰的复杂度进化路线：暴力能做，但不是最优；换对数据结构，复杂度能降一个量级。我先把结论放在表格里：

这组对比特别直观：想办法让每个元素"入一次、出一次"而不是被反复处理，往往就能得到线性复杂度。逆波兰求值里的每个数字最多入栈一次、出栈一次；单调队列里的每个下标最多入队一次、出队一次；桶排序里的每个元素也最多放入和取出一次。做题时养成"分析每个元素被访问了几次"的习惯，很多看似复杂的题目就能找到优化方向。

2. 150 逆波兰表达式求值：栈的经典应用

2.1 题目解析与数据流模拟

LeetCode 150 给出的输入形如["2","1","+","3","*"]，表示后缀表达式(2 + 1) * 3，要求返回 9。再比如["4","13","5","/","+"]表示4 + (13 / 5)，结果是 6。

解题思路就是一个栈模拟。我习惯把规则拆成三步：

1. 遇到数字，直接压栈。
2. 遇到运算符，从栈中弹出两个数，注意先弹出的是右操作数，后弹出的是左操作数。
3. 按照运算符计算结果，把结果压回栈中。

拿["2","1","+","3","*"]走一遍：先入栈 2，再入栈 1，遇到+，弹出 1 和 2，计算 2 + 1 = 3，压回 3；遇到数字 3 压栈，栈里是 [3, 3]；遇到*，弹出右操作数 3 和左操作数 3，计算 3 * 3 = 9，压回 9。扫描结束，栈顶元素就是答案。

整个过程非常机械，但它背后藏着一个重要思想：后缀表达式不存在歧义，因为每个运算符的优先级已经通过"位置"表达清楚了。你不用像中缀表达式那样去维护两个栈（一个操作数栈、一个运算符栈）来处理括号和优先级。这也是为什么很多计算器在内部转换时会用到逆波兰表达式。

2.2 代码实现

我写了 Python 版本，这是最贴近思路的写法：

def evalRPN(tokens: List[str]) -> int: stack = [] for token in tokens: if token in {"+", "-", "*", "/"}: b = stack.pop() a = stack.pop() if token == "+": res = a + b elif token == "-": res = a - b elif token == "*": res = a * b else: # "/" res = int(a / b) stack.append(res) else: stack.append(int(token)) return stack[0]

运算符出现时为什么要弹两个数？因为要严格区分a - b和b - a。后缀表达式中，运算符左侧的操作数先入栈，右侧的操作数后入栈，所以弹出顺序一定是"先右后左"。如果搞反了，["4","13","5","/","+"]会算成5 / 13而不是13 / 5，结果直接错。

2.3 易错点：除法与负数取整的坑

这道题最大的坑不是栈操作，而是除法。题目要求用整数除法，且结果向零截断。在 C++/Java 中，-3 / 2的结果是-1（向零取整）；但在 Python 中，-3 // 2的结果是-2（向负无穷取整）。如果直接写a // b，遇到负数运算就会和预期不符。

解决办法是先把除法转成浮点，再用int()截断向零取整：int(a / b)。这一步很关键，我第一次刷的时候就是漏了它，提交后有一组负数用例挂了。

另一个值得注意的点是：tokens里的元素全是字符串，数字可能是"-2"这样的负数，也可能是多位数"12"。写int(token)时不需要额外判断符号，Python 的int()完全支持。

2.4 面试可以说的扩展方向

逆波兰表达式求值在真实工程中也有对应场景。编译原理中后缀表达式的计算就是要借助栈完成；一些脚本引擎在解析用户输入时，也会先把中缀表达式转成后缀，再通过类似逻辑求值。面试官要是让你"手写一个计算器"，你不用把整个转换步骤写得特别复杂，先把中缀转后缀的思路说清楚，再给出上面的求值过程，基本就能过关。

3. 239 滑动窗口最大值：单调队列的威力

3.1 暴力解与为什么不能用普通优先队列

239 题目很经典：给定数组nums，有一个大小为k的滑动窗口，从数组最左端移动到最右端，每次移动一位，要求输出每个窗口内的最大值。

最直观的暴力解法是固定窗口起点，遍历窗口内k个元素求最大值，时间复杂度 O(n*k)，在n和k都很大时直接超时。优化目标很明确：能不能让每个元素只被处理常数次，整体做到 O(n)？

有人说"用优先队列（最大堆）啊，堆顶就是最大值"。这个思路方向对，但有一个现实问题：窗口会移动，堆顶元素可能已经不在窗口内，需要把它删掉。可是普通的堆只支持删除堆顶，不支持快速删除某个任意元素。虽然可以延迟删除，也就是用一个哈希表维护"无效元素"的计数，等无效元素到堆顶时再弹出，但实现起来代码量和管理复杂度都不小。

单调队列的优势在于：它利用双端队列在 O(1) 时间内从队尾弹出无用元素，从队头弹出过期元素，天然适配窗口滑动这个场景。每个元素最多入队一次、出队一次，总复杂度 O(n)。面试时如果时间有限，直接写单调队列是最稳妥的选择。

3.2 单调队列维护规则：画图理解

单调队列到底在维护什么？一句话：队列中存储的是数组下标，且这些下标对应的值从左到右严格递减。队首下标对应的值就是当前窗口的最大值。

拿示例nums = [1,3,-1,-3,5,3,6,7]，k = 3演示：

• 初始 i=0，队列空，加入 0。队列[0]。
• i=1，值为3，弹出队尾下标0（因为 nums[0]=1 <= 3），加入1。队列[1]。
• i=2，值为-1，不弹出，加入2。队列[1,2]。窗口满，队首1对应值3，输出3。
• i=3，值为-3，不弹出，加入3。队列[1,2,3]。输出队首3。
• i=4，值为5，先将队首过期元素弹出？此时窗口左边界为2，队首1 < 2，弹出1。然后弹出队尾所有 <=5 的下标，即 2、3 都弹出，再加入4。队列[4]，输出5。
• 后续依次得到 5,6,7。

规则提炼成四步：

1. 若队首下标已经滑出窗口（即队首 < 当前窗口左边界），弹出队首。
2. 从队尾弹出所有"值小于等于当前元素值"的下标。为什么小于等于也弹？因为如果当前元素更大，旧元素在窗口内永远不会成为最大值；如果相等，保留更靠后的下标也更有优势（更晚过期）。
3. 将当前下标压入队尾。
4. 如果当前索引已经达到k-1，说明窗口已经完整滑入，此时队首下标对应的值就是窗口最大值。

这里有个细节，步骤 1 和步骤 2 的顺序可以调整吗？可以，但推荐先处理过期元素，再维护单调性。因为如果先加入新元素再处理过期元素，可能会把刚加入的下标也误判为过期，需要多写逻辑。按"先过期、后单调、再入队"的顺序，边界好记很多。

3.3 代码实现

Python 使用collections.deque，代码很短：

from collections import deque def maxSlidingWindow(nums: List[int], k: int) -> List[int]: dq = deque() ans = [] for i in range(len(nums)): # 1. 弹出不在窗口内的队首 if dq and dq[0] < i - k + 1: dq.popleft() # 2. 弹出所有 <= 当前值的队尾元素 while dq and nums[dq[-1]] <= nums[i]: dq.pop() # 3. 加入当前下标 dq.append(i) # 4. 窗口满后记录最大值 if i >= k - 1: ans.append(nums[dq[0]]) return ans

这里判断过期的条件是dq[0] < i - k + 1，其中i - k + 1就是当前窗口的左边界下标。比如 i=4，k=3，左边界为 2，下标 1 已经滑出窗口，所以弹出。如果写成<=就错了，会把左边界本身也弹出，导致当左边界正好是最大值时出错。

3.4 容易踩的坑

第一个坑是用列表 List 替代 deque。Python 的list.pop(0)是 O(n) 操作，在 n 很大时会让整体复杂度假性回到 O(n²)。面试时手写代码可能不在意库函数，但真在 OJ 上跑，性能差距非常明显。

第二个坑是下标和值分不清。单调队列里存的是下标，不是值。不熟练时很容易写dq存值，然后发现无法判断过期（只能判断最大值，不知道它在窗口里的位置）。所有与"窗口边界"有关的检查都依赖下标，因此请把"下标入队"刻进脑子。

第三个坑是单调条件使用<还是<=。我建议用<=，即弹出所有队尾值小于等于当前值的下标。这样做能保证相等的元素只保留最新的一个，从而减少无用元素的堆积。如果你用<，队列里可能会同时存在多个相等的最大值，虽然队首最大值依然正确，但队列长度会更长，清理过期元素时可能要多循环几轮。实际测试用<=更稳健。

第四个坑是不模拟只背代码。单调队列比普通栈题抽象，必须自己拿笔画一遍队列变化。我每次教朋友这道题，都会要求他们手动写出[4,2,0,3,2,5]的队列快照，写完全部边界就懂了。

4. 347 前 K 个高频元素：从频率统计到 TopK

4.1 第一步：哈希表统计频率

题目要求返回数组中出现频率最高的前 K 个元素。比如nums = [1,1,1,2,2,3]，k = 2，返回[1,2]。

第一步没有悬念，用哈希表统计每个元素的出现次数。Python 直接collections.Counter，或者手动dict。这一步时间复杂度 O(n)，空间复杂度 O(n)。统计完成后，问题变成：有 m 个不同的元素，每个元素带一个权重（频率），需要找出权重最大的前 K 个。

4.2 TopK 方案的取舍：为什么选小顶堆而不是大顶堆

拿到频率后，最简单的方法是按频率从大到小排序，取前 K 个，时间复杂度 O(m log m)。但很多场景下 m 很大，K 很小，排序显得浪费。标准解法是维护一个小顶堆，堆的大小保持在 K，堆顶存放这 K 个元素中频率最小的那个。每当遍历一个元素，如果它的频率大于堆顶频率，就弹出堆顶，放入这个新元素。遍历结束后，堆里剩下的就是前 K 高频。

为什么必须用"小顶堆"而不是"大顶堆"？因为堆大小固定为 K 时，我们需要知道"当前 K 个候选里谁最弱"，从而决定新元素是否值得替换。小顶堆的堆顶正好是"当前最弱"的那个，比较方便；如果用大顶堆，堆顶是"最强"的，你根本不知道该淘汰谁，也就无法维护前 K 大。

补充一下，堆元素存储形式是(频率, 元素值)。如果只存频率而不存元素值，最后没法还原数字；Python 的 heapq 会先比较元组第一个元素，频率相同再比较元素值，这没问题。

4.3 小顶堆实现

import heapq from collections import Counter def topKFrequent(nums: List[int], k: int) -> List[int]: freq = Counter(nums) heap = [] for num, cnt in freq.items(): heapq.heappush(heap, (cnt, num)) if len(heap) > k: heapq.heappop(heap) return [item[1] for item in heap]

这段代码有两个注意点。第一，heapq默认是小顶堆，直接能用，不需要像 C++ 那样priority_queue<int, vector<int>, greater<int>>，但如果面试要求用 Java，就得在 PriorityQueue 构造函数里传比较器，让频率小的优先。第二，当len(heap) > k才弹出，可以避免多弹掉本应保留的元素；判断放在 push 之后更简洁，题目保证 k 小于等于不同元素个数，不会出现堆空的情况。

如果你希望返回结果按频率从高到低排序，可以在返回前对heap做一次sorted或直接倒序输出。LeetCode 对本题的返回顺序没有硬性要求，所以怎么返回都对。

4.4 桶排序：把 O(n log k) 优化到 O(n)

追求极致的同学可以写桶排序。思路是：频率的范围是 1 到 n，所以我们创建n + 1个桶，下标表示频率，桶里放对应频率的元素。统计完成后，从高频率桶向低频率桶遍历，把元素加入到结果中，直到取满 K 个。

def topKFrequent(nums: List[int], k: int) -> List[int]: freq = Counter(nums) buckets = [[] for _ in range(len(nums) + 1)] for num, cnt in freq.items(): buckets[cnt].append(num) res = [] for i in range(len(buckets) - 1, 0, -1): for num in buckets[i]: res.append(num) if len(res) == k: return res

这个写法时间复杂度 O(n)，因为桶的数量是 n+1，遍历一次完事，且不需要排序。面试时如果你能先讲堆方案、再补充桶排序优化，会显得你基本功很扎实。

4.5 相关扩展：堆和队列在生产环境中的影子

我注意到这组热词里，大量出现消息队列选型、线程池阻塞队列选择、Kafka/RabbitMQ/RocketMQ 对比等内容。其实这些生产组件离不了"队列"这个基础形态：先进先出、缓冲削峰、生产者消费者模型。堆也广泛用于任务调度中的优先级队列、定时器的延迟队列。算法题里的单调队列、优先队列，正是理解这些工程组件的最小原子单位。

当然，生产环境的消息队列远比算法里的队列复杂得多，还涉及分布式一致性、数据持久化、重复消费等。刷完这道题，再去读 Kafka 或 RocketMQ 的文档，你对"队列"的理解会多一层直观感受：它们不过是把基础数据结构延伸到了分布式系统里。这也是我一直觉得"数据结构基础题值得反复刷"的原因——它们永远不会过时。

5. 总结：栈与队列专题的实战套路

5.1 从三道题提炼出的解题模板

刷完整组题，我给自己总结了一张"数据结构速查表"：

这个表不是死教条，而是用"特征触发"的方式帮自己快速定位。做题前先用 30 秒问自己：题目有没有"最近"？有没有"窗口"？有没有"第 K 大"？答案基本就出来了。

5.2 刷完后的认知升级：数据结构不是死板的容器

栈和队列学到最后，你会意识到它们不只是"容器"，更是一种"约束"。栈约束你只能从顶部操作，所以它天然适合保存"待办但最晚处理"的事情；队列约束你只能从一端进、另一端出，所以它适合体现公平和秩序。单调队列和优先队列则是在约束之上增加"排序"或"淘汰"规则，本质上是通过删除那些"永远不可能成为答案"的元素来降低复杂度。

这种思维特别像日常生活中的排队：普通队伍是先进先出，VIP 通道可能插队（优先级队列），而滑动窗口最大值更像是一排队伍里你只需要记住"目前最厉害的那个人是谁"，当他离开时你要知道下一个是谁。把抽象的算法还原成具体场景，代码就不会写得迷迷糊糊。

5.3 面试与实战小贴士

最后分享几个实战建议：

第一，优先队列可以大胆用。面试官一般不会要求你手写堆，直接用heapq或priority_queue即可，但你要能解释"为什么 O(n log k)"，以及小顶堆与大顶堆的区别。第二，单调队列必须能手写。因为它依赖双端队列的底层操作，很多面试官会要求你实现完整的维护过程。第三，拿到题先问约束：n 有多大？k 有多大？内存限制多少？这些条件直接影响方案选择，比如 n 极大且不能全量加载时，可能要用分布式计数，而不是直接Counter。

我个人刷这三题刷了差不多三轮，每轮都有新理解。第一轮只会背模板，第二轮搞清楚单调队列为什么能保证队首最大，第三轮才真正体会到"过期剔除+单调性维护"是一对组合拳。如果让我给一个最有价值的技巧，那就是：滑动窗口的题一定要画图。把窗口位置和队列状态一行一行画出来，画到三次以上，边界条件就永远忘不掉了。栈和队列看起来简单，把它们的变化画出来，比盲目刷十道题都有用。