企业官网建设流程全解析

补档两个字，听起来体面，实际上是计划没完成时最后一块遮羞布。Day9那篇栈与队列总结我写到凌晨两点，以为把 LC 225、LC 232 两道基础题搞完就算过关了，结果真正的大头——LC 150、LC 239、LC 347 三道压轴题，硬生生拖了一周。今天这篇 Day10 补档，把这三道题一次性收掉。它们刚好对应栈、队列、优先队列三种容器的核心用法：逆波兰表达式求值考的是栈的“后进先出”到底解决什么问题，滑动窗口最大值考的是双端队列怎么在 O(n) 时间里维护窗口候选值，前 K 个高频元素则是哈希表加小根堆的经典组合。如果你也在做算法复健，这三题做完，你对“栈与队列”的理解才算是真正闭环。

1. 为什么压轴题不是“补缺”，而是整个栈队列章节的收口

1.1 三道题覆盖了三种完全不同的容器

很多人把“栈与队列”当成两个简单到不需要复习的知识点：栈就是先进后出，队列就是先进先出。但 LeetCode 在这个章节里真正想考察的，是你在遇到具体问题时能不能判断该用哪个容器、为什么要用这个容器、以及怎么针对容器的特性做优化。

LC 150 用的是栈。它的核心场景是运算顺序被延迟了，必须把前面的操作数暂存起来，等遇到运算符再取出来计算。

LC 239 用的是双端队列（Deque）。它已经不是简单的先进先出了，而是要在队列两端同时做操作：队头淘汰过期元素，队尾淘汰“以后不可能再用到”的较小元素。这种结构在教科书里叫双端队列，但在算法题里它通常被称作单调队列，因为整个队列维护的是一个单调递减的候选序列。

LC 347 用的是优先队列（堆）。严格来说，它和“先进先出”这个定义已经没什么关系了，但它被放在栈与队列这个大章节里是有道理的：优先队列本质上也是一种队列，只是出队顺序由优先级决定，而不是由插入顺序决定。如果你连 PriorityQueue 都还停留在“会用但不知道为什么这么用”的阶段，这道题就是最好的补课机会。

1.2 从难度梯度看复健节奏

这三道题不是随意凑在一起的。从数据结构的复杂度看，LC 150 是最温和的入门，只要想清楚“后进先出”和表达式求值的关系，基本不会卡太久。LC 239 直接上一个台阶，它要求你放弃“每次窗口滑动都重新扫描”的直觉，接受一个反直觉的结论：很多元素根本不需要留在候选队列里，因为它们已经注定不可能成为最大值。LC 347 则是把栈队列章节推向了算法的综合场景，哈希表的计数配合小根堆的淘汰，复杂度从 O(n log n) 降到 O(n log k)，这个过程本身就是经典的“不能在所有元素上做全局排序”的思维训练。

1.3 复健的标准不是“能 AC”，而是“能讲出思路”

我给这三道题定了个简单的复健标准：不看题解，能自己写出 AC 代码；写完能把时间复杂度和空间复杂度算清楚；过一天后能不看代码把核心思路复述出来。这三条同时满足，才算真正拿下一个题。单纯把题解背下来然后当天 AC，第二天基本就忘光了，那种状态不叫复健，叫安慰自己。

2. LC 150 逆波兰表达式求值：栈的“后进先出”不是语法，而是答案

2.1 后缀表达式的本质就是“延迟计算”

逆波兰表达式也叫后缀表达式，它的特点是运算符写在操作数之后。像3 4 + 5 *这样的表达式，人眼一开始看会很别扭，因为我们的直觉是(3 + 4) * 5。但反过来想，后缀表达式其实已经把运算符优先级和括号全部抹平了，计算过程只需要严格从左到右扫描一遍。

栈在这里的作用极其自然：遇到数字先放着，因为不知道左边这个数到底要不要和后面的数先算；遇到运算符，说明前面两个数该算了，就把最近的两个数取出来做运算。整个过程不需要回溯、不需要递归、不需要维护优先级表，因为后缀表达式本身已经把计算的先后顺序编码在位置里了。

这其实就是生活里排队的场景：先来的人不一定先处理，栈允许你“后来居上”。表达式求值用的是栈而不是队列，就是因为最近遇到的数字才最可能在下一个运算符到来时被使用，这种对“最近性”的自然维护只有栈能做到。

2.2 一份可以直接抄的 Java 实现

class Solution { public int evalRPN(String[] tokens) { Deque<Integer> stack = new ArrayDeque<>(); for (String token : tokens) { switch (token) { case "+": stack.push(stack.pop() + stack.pop()); break; case "-": int a = stack.pop(); int b = stack.pop(); stack.push(b - a); break; case "*": stack.push(stack.pop() * stack.pop()); break; case "/": int divisor = stack.pop(); int dividend = stack.pop(); stack.push(dividend / divisor); break; default: stack.push(Integer.parseInt(token)); } } return stack.pop(); } }

这里有一个细节值得单独说：栈顶操作要用Deque<Integer> stack = new ArrayDeque<>()，而不是Stack<Integer>。Stack是 Java 里遗留的同步类，性能差，而且它继承了 Vector 的一些我们根本不需要的接口。刷题和日常开发里都建议用ArrayDeque代替它。

2.3 减法和除法的两个经典坑

第一个坑是操作数顺序。做减法时，第一次pop()出来的是后来入栈的a，第二次pop()出来的是更早入栈的b。后缀表达式3 4 -实际要做的是3 - 4，也就是b - a，而不是a - b。我复健时第一次写 LC 150，就栽在这上面，减法和除法的符号死活不对，一调试才发现顺序反了。

第二个坑是除法的截断方向。LeetCode 这道题要求除法向零截断，Java 的整数除法本身就是向零截断，所以dividend / divisor直接写就行。但如果你在 Python 里做这题，/得到的是浮点数，需要自己处理截断逻辑；在 C++ 的早期标准里负整数除法是向负无穷截断，也容易出问题。同一个题在不同语言里的隐藏差异，恰恰是复健过程中值得记录的笔记点。

2.4 这道题给复健者的额外启示

LC 150 看起来只是简单的“遇到数字入栈”，但它的思想和很多看似不相关的题是相通的。比如括号匹配、函数调用栈、回文判断，核心都是“最近的信息要先处理”。这个直觉建立起来之后，再去看后面二叉树的前序遍历和中序遍历的迭代写法，你会发现自己对栈的运用已经有了质的提升。

3. LC 239 滑动窗口最大值：单调队列的核心是“淘汰没有未来的元素”

3.1 暴力解法为什么不够

先看一眼题目要求：给你一个整数数组nums，有一个大小为k的滑动窗口从数组的最左端移动到最右端，要求返回每次滑动窗口中的最大值。

最简单的做法是每个窗口都遍历一遍 k 个元素，找最大值。这样做的时间复杂度是 O(n * k)。看起来不差，但极端情况下 k 接近 n/2，性能直接退化成 O(n²)。我在复健时先写了暴力版本跑了一下，数据量大一点就明显感觉到卡顿。

优化的突破口在于：窗口滑动时，窗口里的元素只删掉一个、增加一个，绝大多数元素是不变的。如果每次都重新扫描所有元素，等于把上一轮已经算过的信息全部扔掉。这就引出了单调队列的思路。

3.2 单调队列的三大操作

用一个双端队列来存放候选元素的下标，从头到尾的元素值保持递减。每次窗口向右移动一位，做三件事：

1. 淘汰过期元素：队头的下标如果已经离开了当前窗口（i - k），就把队头弹出。
2. 淘汰“没有未来”的元素：从队尾开始，把值小于等于新元素的下标全部弹出。因为新元素比它们更大，而且在窗口里更晚过期，只要新元素还在，它们就不可能再从队头作为最大值被输出。
3. 把当前下标加入队尾。

做完这三步，当前窗口的最大值就是队头下标对应的值。

3.3 用例子推演一遍，比背代码强十倍

拿nums = [1,3,-1,-3,5,3,6,7]，k = 3来说：

• i=0，窗口[1]，队列[0]，最大值 1。
• i=1，窗口[1,3]，新元素 3 比队尾 1 大，弹出 0，入队下标 1，队列[1]。
• i=2，窗口[1,3,-1]，-1 比队尾 3 小，直接入队，队列[1,2]，最大值 3。
• i=3，窗口[3,-1,-3]，先检查队头 1 是否过期（1 <= 3-3=0？否），队尾 -3 比 -1 小，入队，队列[1,2,3]，最大值 3。
• i=4，窗口[-1,-3,5]，队头 1 过期弹出（1 <= 4-3=1），队尾 -3、-1 都小于 5，全部弹出，入队 4，队列[4]，最大值 5。

输出是[3,3,5,5,6,7]。走完这个例子，基本能把单调队列的操作逻辑记住。

3.4 存下标而不是存值，是很多人忽略的关键

我第一次写这道题时，队列里存的是元素值，结果发现一个致命问题：队头元素过期时，光看值根本不知道它到底在不在当前窗口里，因为你不知道它的下标。必须存下标，才能精确判断它是否已经滑出了窗口。

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] res = new int[n - k + 1]; Deque<Integer> deque = new ArrayDeque<>(); for (int i = 0; i < n; i++) { if (!deque.isEmpty() && deque.peekFirst() <= i - k) { deque.pollFirst(); } while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) { deque.pollLast(); } deque.offerLast(i); if (i >= k - 1) { res[i - k + 1] = nums[deque.peekFirst()]; } } return res; } }

3.5 等号的处理方式也有一点讲究

这里有一个经常被问到的细节：队尾淘汰条件要不要带等号？用nums[deque.peekLast()] <= nums[i]表示新元素更大或相等时，旧元素直接淘汰。为什么相等也要淘汰？因为相等的情况下，新元素的下标更大，意味着它在窗口里存活得更久，淘汰旧元素既不影响最大值，还能减少队列长度。这就是“使用<=”的出发点。

3.6 和生产环境里的队列思想对比

如果你平时写业务代码，可能接触过阻塞队列、线程池队列这些概念。算法里的单调队列和它们本质上都在解决同一个问题：什么时候需要保留一个元素，什么时候可以果断丢弃。线程池选择ArrayBlockingQueue还是LinkedBlockingQueue的时候，考虑的是容量、锁粒度、内存分布；单调队列考虑的是值是否还有可能成为未来的输出。理解“淘汰策略”这件事，远比背一个题重要。

4. LC 347 前 K 个高频元素：小根堆把全局排序的想法扔掉了

4.1 哈希表计数是第一步，不是难点

题目要求返回数组里出现频率最高的前 K 个元素。第一反应当然是统计频率，这一步用哈希表就能完成：

Map<Integer, Integer> freq = new HashMap<>(); for (int num : nums) { freq.merge(num, 1, Integer::sum); }

到这里复杂度已经是 O(n)，真正的分歧在于下一步：怎么从所有不同的元素中找出频率最高的 K 个。

4.2 为什么不该用大根堆堆满所有元素

很多人第一反应是把所有元素塞进一个大根堆，然后弹出 K 次。这样做确实能得到结果，但代价是全量建堆，每次插入是 O(log n)，总复杂度 O(n log n)。在 n 很大的时候，这个解法并没有比“对所有频率排序”高明多少。

正确做法是维护一个大小为 K 的小根堆。遍历哈希表的键时，把键塞进堆里；堆的大小一旦超过 K，就把堆顶弹出。因为小根堆的堆顶是堆里频次最小的元素，它最不需要保留，淘汰它之后堆里剩下的一定是目前见过频次最大的 K 个元素。

这样每个元素最多经历一次offer和一次poll，单次操作 O(log K)，整体复杂度 O(n log K)。当 K 远小于 n 的时候，这个优化非常明显。

import java.util.*; class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> freq = new HashMap<>(); for (int num : nums) { freq.merge(num, 1, Integer::sum); } PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b)); for (int key : freq.keySet()) { pq.offer(key); if (pq.size() > k) { pq.poll(); } } int[] ans = new int[k]; for (int i = k - 1; i >= 0; i--) { ans[i] = pq.poll(); } return ans; } }

4.3 出队顺序和输出顺序的关系

这里有个很容易绕晕的点：小根堆里弹出的是频次最小的元素，所以最后出队的顺序是从小到大。如果你要的结果是从大到小输出，就把弹出的元素倒序放进结果数组。我复健时在这个细节上纠结了几分钟，后来总结出一个经验：小根堆保证的是“堆顶永远是可以被丢弃的那个”，它并不保证输出的顺序。

4.4 更极端的解法可以到 O(n)

实际上，LC 347 还有桶排序的解法：用数组下标表示频次，把一个频次对应的所有元素放进同一个桶里，最后从高频桶往低频桶遍历收集 K 个元素。这种做法的复杂度是 O(n)，但空间上需要开到最大频次那么大，数据比较稀疏时反而浪费。

复健的意义在于掌握主线解法，也就是哈希表加小根堆。桶排序可以作为进阶思考，但并不建议作为面试时的首选，因为面试官更希望你先把小根堆的淘汰逻辑讲清楚，而不是一上来就追求看似更优但实现更复杂的方案。

4.5 已经持续三天的“常见错误”

我在 347 题上交过的学费是：写优先队列的比较器时，误把freq.get(key)和key搞混。优先队列里存的是“元素的取值”，但优先级取决于“该元素出现的频次”。Comparator 里边必须写freq.get(a) - freq.get(b)，而不是a - b。这类错误不报错，代码能跑，但堆的顺序完全是乱的。调试这种问题的最佳办法是拿一小段数据跑一遍，把堆里的元素和它们对应的频次一起打印出来，一眼就能看出问题。

5. 三题横向复盘：“用什么容器”的底层判断标准

5.1 一表看懂三种容器的分工

三题的复杂度标在一起之后，能明显看出一个规律：凡是涉及“在一段连续数据里动态维护某个极值”的问题，可以用单调队列把复杂度压到 O(n)；凡是涉及“从大量候选中找到 Top K”的问题，小根堆是最自然的方案，复杂度是 O(n log k)。

5.2 栈的适用场景

栈最适合的场景是“需要延迟处理最近的信息”。表达式求值、括号配对、函数递归的模拟、以及二叉树的前序迭代遍历，都是这个模式。核心判断标准是：我当前遇到的信息，是否需要等一下再处理？如果需要，用一个栈来暂存“最近还没有处理完”的元素，总不会错。

5.3 队列与优先队列的适用场景

队列适合的场景是“先进先出就能满足要求”，典型就是 BFS 层序遍历。双端队列则在“两端都可能需要操作”时出场，滑动窗口最大值只是其中一个代表。

优先队列的适用场景是“处理顺序取决于优先级而不是插入顺序”，比如任务调度、合并 K 个有序链表、求数据流中的中位数。判断标准也很简单：如果每次都要从一堆元素里快速拿出最大或最小的那个，堆就是标准答案。

5.4 给复健者的三个变式思考

光做原题容易形成路径依赖，我在 Day10 收尾时给自己加了三道变式思考题，你也试试：

1. LC 150 如果输入的表达式是中缀表达式，怎么先转成后缀再进行计算？需要额外维护一个运算符栈吗？
2. LC 239 如果窗口里同时要最大值和最小值，能不能用两个单调队列同时维护？
3. LC 347 如果数据量太大，哈希表都放不下，有没有流式处理的近似算法？

这三个变式不需要全部写代码，能想出思路，就算过关。

6. 补档之后的收尾：我把“复健”踩过的两个坑也一起记下来

6.1 复健的坑之一：看题解太快，以为自己会了

复健前三天我犯过一个很典型的错误：题目卡住十分钟就忍不住打开题解，看懂之后恍然大悟，然后 AC，觉得自己厉害了。结果第二天同一道题从头再写，居然又卡在同一个地方。后来我给自己定了个规矩：一道题至少独立想出大方向，哪怕复杂度不是最优，也要先写出一个能跑的版本，再对照题解优化。这个习惯改过来之后，复健效率明显提升。

6.2 复健的坑之二：只刷数量，不做复杂度分析

第二周开始，我每道题都强迫自己写一行复杂度注释，放到代码注释里。LC 239 如果你只知道队列能过，但说不清为什么是 O(n)，那就是没懂；LC 347 如果你不知道小根堆的 log 是从哪里来的，你也没法在面试里解释清楚。复健不是给 LeetCode 刷提交纪录，是把知识点重新焊进脑子里的过程。

6.3 Day11 准备把“栈队列”的剩余尾巴收到二叉树上去

第十天结束，我给自己定了下一个主题：二叉树。LC 144 前序遍历、LC 145 后序遍历、LC 102 层序遍历，这三道题刚好把栈（迭代遍历）和队列（层序 BFS）一起用上。栈与队列这一章学会的容器选择逻辑，到了二叉树上马上又要再验证一遍。这两个章节的知识不是割裂的，反而是一条完整的链路：栈和队列是最基础的容器，二叉树是它们的第一个大型实战现场。

至于“补档”这件事，我不想再发生了。算法复健最怕的不是遇到难题，而是节奏中断之后那种“今天算了吧，明天再补”的滑坡。我的对策很简单：Day11 开始，不管当天文章写完有没有人看，必须在睡前把当日总结写完。复健这件事，规律的重复比一时的灵感更值钱。