企业官网建设流程全解析

代码随想录训练营刷到第10天，栈和队列专题正式进入硬仗阶段。150.逆波兰表达式求值、239.滑动窗口最大值、347.前K个高频元素，这三道题摆在一起，表面上是三个独立的LeetCode题目，实际上暗含一条完整的数据结构进阶链路：先玩明白栈，再理解队列的变形，最后把堆拉进来打配合。如果你正在跟训练营的进度，或者准备面试想练手，这一天的三道题建议一口气刷完，它们分别对应三类最常考的数据结构，一道比一道有嚼劲。

先说结论：150题是栈的纯应用，考察对后进先出的条件反射；239题考队列的定制化改造，是单调队列的招牌题；347题则是哈希表与堆的组合拳，也是最容易在面试中“答完还有追问”的题。三道题都不算超难题，但每道题的优化空间都值得深挖一遍。这篇文章我会按“思路拆解 → 原理讲解 → 代码实现 → 避坑记录”的顺序展开，尽量把每一道题为什么这么解、坑在哪里讲透。

1. 三道题整体拆解：为什么值得放在同一天刷

1.1 从题目看数据结构进阶路径

我刷完这三道题后最大的感触是：题目安排顺序是有讲究的。150题本质是栈的操作型应用，你不需要理解多高深的算法思想，只要严格遵循“数字入栈、运算符出栈运算再压栈”的规则执行即可，它考查的是对栈的后进先出特性有没有形成本能反应。239题是队列的改造型应用，普通队列解决不了滑动窗口最大值的问题，必须对入队出队逻辑做定制，演化出单调队列这个概念，这里考查的已经不是“会不会用队列”，而是“能不能根据业务需求给数据结构做裁剪”。347题则是堆和哈希表的组合型应用，哈希表负责统计频率，堆负责维护前K个，两者各司其职。

这三题放到一起，相当于把“数据结构只是工具箱里的工具，真正值钱的是根据场景挑工具、改工具”这个思想完整过了一遍。很多人在刷题初期容易陷入“背模板”的误区，觉得栈就是配对、队列就是BFS、堆就是TopK，但真正到了239这种需要改造队列的题目，会突然发现模板不好用了。这恰恰是训练营把三道题放在一天的原因——推着你从“认识容器”走向“理解容器”。

1.2 难度梯度与核心考点

先用一个表格把三道题的关键信息列出来，方便对照：

这个表格值得多看两眼。复杂度上最惊艳的是239题：暴力解法是O(n×k)，优化后是O(n)，这是质的飞跃，也是这道题被称为“单调队列招牌题”的根本原因。347题则完全不同，它本身并不复杂，但如果用大顶堆或者直接全排序，复杂度会升到O(n log n)，用小顶堆则稳定在O(n log k)，体现的是“别做多余计算”的工程思维。

1.3 时间分配建议

我在实际刷的时候，150题卡在了减法和除法的操作顺序上，来回调了差不多20分钟；239题即便知道单调队列的思路，自己写还是容易在pop逻辑上翻车，前后折腾了快一小时；347题反而最顺利，因为思路非常固定，先统计频率再维护大小为k的堆，30分钟以内就能搞定。

如果你今天刚开始刷这三道题，我建议这样分配时间：150题控制在30分钟内，239题可以放宽到1小时，347题30到40分钟。239题值得多花时间，因为它背后的“单调性维护”思想在后续很多题目里都能复用，比如求滑动窗口最小值、求区间最值差，甚至一些二维滑动窗口的变体题，底层都是同一套逻辑。

2. 150. 逆波兰表达式求值：栈的教科书级应用

2.1 后缀表达式的设计初衷

先解决一个很多人没想过的问题：逆波兰表达式（也叫后缀表达式）到底解决了什么？我们平时写“1 + 2”叫中缀表达式，人看着舒服，但对计算机来说相当麻烦。因为中缀表达式里有优先级和括号，比如“1 + 2 * 3”必须先算乘法，计算机如果直接处理，需要维护运算符优先级状态，甚至要把表达式解析成语法树。

后缀表达式的写法是“1 2 +”，运算符跟在操作数后面。这个形式有个天然优势：完全不需要括号，也不需要优先级规则。求值过程就是从左到右扫一遍，遇到数字就压栈，遇到运算符就弹出两个数字做运算，结果再压回栈，扫完整个表达式后栈里只剩一个数，那就是答案。整个过程规则统一，没有任何分支判断优先级的逻辑。

这也是早期计算器和编译原理课程里经常用逆波兰表达式求值的原因。很多科学计算器内部就是把用户输入的中缀表达式先转换成后缀表达式，再按这个过程求值。你手写这道题，其实就是在模拟计算器的核心计算模块。

2.2 算法流程与C++实现

算法流程非常固定，四句话就能说完：

• 遇到数字，转换成整数后压入栈
• 遇到运算符，弹出栈顶的两个元素
• 先弹出的记为 num1，后弹出的记为 num2
• 用 num2 和 num1 做对应运算，结果压回栈

直接上C++代码：

class Solution { public: int evalRPN(vector<string>& tokens) { stack<long long> st; for (const string& token : tokens) { if (token == "+" || token == "-" || token == "*" || token == "/") { long long num1 = st.top(); st.pop(); long long num2 = st.top(); st.pop(); if (token == "+") st.push(num2 + num1); else if (token == "-") st.push(num2 - num1); else if (token == "*") st.push(num2 * num1); else st.push(num2 / num1); } else { st.push(stoll(token)); } } return static_cast<int>(st.top()); } };

代码里我刻意把栈的类型声明成 long long，因为力扣的测试用例会出现中间结果超过 int 范围的场景。刷题时宁可多留一点余量，也不要因为溢出卡一个提交。

2.3 操作顺序是最容易踩的坑

这个坑我必须单独拿出来说，因为几乎每个第一次写这道题的人都会掉进去。对于“1 2 -”，正确的计算是“1 - 2 = -1”。但在出栈时，先弹出的是 2（栈顶元素），后弹出的是 1。此时 num1=2，num2=1，如果代码里写成 num1 - num2，得到的是“2 - 1 = 1”，直接错了。

因此减法和除法必须用 num2 作被减数/被除数，用 num1 作减数/除数，也就是代码里写的 num2 - num1 和 num2 / num1。

除法还有一个语言层面的细节需要注意：C++ 的整数除法是向零截断的，题目明确要求的正是这个行为，所以直接用“/”没问题。但如果你用 Python 刷，它的“//”是向下取整，负数除法的行为跟 C++ 不一致，比如 -3 // 2 在 Python 里是 -2，在 C++ 里是 -1，必须额外处理。用 Python 的话可以写成 int(num2 / num1) 来规避。

2.4 复杂度与边界场景补充

时间复杂度和空间复杂度都是 O(n)，n 是 tokens 数组的长度。每个元素最多入栈一次、出栈一次，总操作次数和元素个数线性相关。

几个容易忽略的边界点：

• 表达式可能只有一个数字，比如 tokens = ["18"]，此时循环不会执行，直接返回 18，代码能正确处理
• 元素可能带负号，比如 "-11"，C++ 的 stoll 可以解析负数，不需要手动处理符号
• 中间运算结果用 long long 存储，避免极端用例溢出

另外提一句，如果你追求更少的代码量，可以把四则运算的分支抽成 lambda 表达式配合 switch 简化，但可读性会差一些。面试场景下，像上面这种直白的写法反而更容易讲清楚思路。

3. 239. 滑动窗口最大值：从暴力到单调队列

3.1 暴力解法的局限

题目要求输出一个大小为 k 的滑动窗口在数组上从左滑到右时，每个窗口内的最大值。暴力解法非常直观：每次窗口移动，遍历窗口内 k 个数，取最大值，代码写出来很简单，但时间复杂度是 O(n×k)。

假设 n 是 10万，k 是 5万，那就是 5 亿次操作，绝大多数判题环境会直接超时。暴力为什么慢？因为在窗口滑动过程中，很多元素被反复比较。窗口从位置 i 滑到位置 i+1 时，只有最左边的元素被移除、最右边新增一个元素，中间 k-1 个元素其实没变，它们的最大值原本是可以复用的，暴力法却完全忽略了这一点。

这就是单调队列出现的理由：用额外空间记录窗口内有用的信息，把每个元素进队列、出队列的次数压到常数级，从而整体做到 O(n)。

3.2 单调队列的核心设计

单调队列名字听着吓人，本质上就是一个普通的双端队列 deque，只不过维护了一个规则：

队列里的元素，从队首到队尾，值严格递减（或者递增）。队首永远是当前窗口的最大值。

如何维持这个递减性？关键在入队操作。每次新元素要入队时，先把队尾所有比它小的元素全部弹出，再把它放到队尾。可以这样想：一队人按顺序排队，新来的人如果比前面的人都高，那他后面的人哪怕个子再高，在这支队伍里也不可能成为队首最大值，因为新来的人已经把他们都“挡住”了。与其留着，不如直接清掉。

窗口滑动时对应的出队操作是：当窗口最左边的元素离开时，检查一下队首是不是这个元素，如果是，就把队首弹出，因为它已经不在窗口范围内了。

这里最精妙的地方在于：pop 操作只需要比较“即将离开窗口的元素”和“队首元素”。如果一个元素在窗口内曾经被更靠后的更大元素淘汰了，那它在之前的 push 里早就出队了，根本不需要在窗口滑出时再处理。因此 pop 的判据是值相等才出队，而不是无条件出队。

3.3 完整实现与关键步骤解析

先写一个独立的单调队列类，把逻辑封装好，主流程会特别清爽：

class MonotonicQueue { private: deque<int> que; public: void pop(int value) { // 只有当要移除的元素恰好是队首时才出队 if (!que.empty() && value == que.front()) { que.pop_front(); } } void push(int value) { // 维持队首到队尾的单调递减 while (!que.empty() && value > que.back()) { que.pop_back(); } que.push_back(value); } int front() { return que.front(); } }; class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { MonotonicQueue mq; vector<int> result; for (int i = 0; i < k; i++) { mq.push(nums[i]); } result.push_back(mq.front()); for (int i = k; i < nums.size(); i++) { mq.pop(nums[i - k]); // 移除滑出窗口的元素 mq.push(nums[i]); // 加入新滑入窗口的元素 result.push_back(mq.front()); } return result; } };

主流程是标准的窗口滑动套路：先初始化第一个窗口，然后每移动一步，先 pop 掉离开窗口的元素，再 push 进入窗口的元素，最后取队首。整个过程没有额外的循环，时间复杂度 O(n)。

理解 pop 为什么要判断值相等，是这道题能不能真正吃透的分水岭。举个例子：窗口内是 [5, 3]，队列里存的是 [5, 3]。当窗口继续滑动，3 要离开窗口时，比较发现队列队首是 5，和 3 不相等，所以不会把队首删掉。而队列里的 3 在离开窗口之前，要么已经被某个更大的元素在 push 时弹掉了，要么还在队尾，离开时队首 5 依然能代表当前窗口最大值。真正需要触发 pop 的只有一种情况：窗口左边界移除的元素恰好还留在队首，比如窗口从 [5, 3] 变成 [3, 4]，此时 5 离开窗口，队首刚好是 5，才需要把队首弹出去。

3.4 常见理解误区

误区一：以为单调队列需要每次都清空重建。实际上单调队列是不需要重建的，元素一旦被淘汰是真的丢弃，后续窗口怎么滑动也不会再来。

误区二：不知道为什么要用 deque。普通队列只能一端出队一端入队，但单调队列的 push 操作需要从队尾弹出元素，这要求双端操作能力，deque 是唯一合适的容器。

误区三：以为“队首永远是当前窗口最大值”是单调队列的性质，其实是“单调递减队列”的性质。如果设置成队尾到队首递减，也就是队首最小，得到的就是滑动窗口最小值。道理一样，方向相反。

这道题的变体也很常见，比如求滑动窗口最小值、求滑动窗口中的最值差，逻辑都可以直接复用，只要把 push 里的比较符号反过来就行。

4. 347. 前 K 个高频元素：哈希表与堆的组合拳

4.1 第一步：频率统计

“前 K 个高频元素”的需求拆开就是两步：先知道每个元素出现了多少次，再找出次数排前 K 的那些元素。第一步没有悬念，用一个哈希表遍历数组，key 存元素，value 存出现次数：

unordered_map<int, int> freq; for (int num : nums) { freq[num]++; }

这一步的时间复杂度是 O(n)，空间复杂度 O(n)，在整个解题方案里是最基础也最稳定的一环。

真正要动脑子的是第二步。有人会想，把哈希表里所有元素按频次从大到小排序，取前 K 个不就行了吗？这样做确实能解出来，时间复杂度是 O(n log n)。但题目有个隐含的优化点：我们只需要前 K 个，并不需要把所有元素都排好序。当 n 很大、K 很小的时候，全排序的浪费相当明显。

4.2 为什么是小顶堆而不是大顶堆

这是整道题最容易产生直觉偏差的地方。大多数人听到“前 K 个最大/最高频”，第一反应是用大顶堆：堆顶是最大元素，取前 K 个直接弹 K 次。但这里有个陷阱。

如果维护一个大顶堆，为了拿到最大频率，你必须把所有元素都放进堆里。因为堆顶只暴露最大值，你无法直接知道哪些是次大的，要拿前 K 个，得先把所有元素入堆，然后再连续弹出 K 次，整个过程复杂度 O(n log n)，和你直接排序没本质区别。

反过来，如果我们维护一个大小固定为 K 的小顶堆，思路就反过来了：堆顶是堆里最小的元素。每当有新的 (频率, 元素) 要加入时，先加进去，如果堆的大小超过 K，就把堆顶的最小频率元素弹出来。这样遍历完所有元素后，堆里留下的恰好是频率最大的 K 个元素，而且堆里始终只存 K 个元素，操作成本从 O(log n) 变成 O(log K)。

关键点：用空间换时间。大顶堆存了所有元素，小顶堆只存 K 个。当 K 远小于 n 时，效率差距非常明显。

我在实际面试和工作中，只要遇到 Top K 类问题，都会先想能不能用小顶堆控制住堆的大小，而不是把所有数据都塞进堆里。这种思维在实时数据流、日志高频词统计等场景里尤其实用。

4.3 堆的代码实现细节

C++ 里直接用 priority_queue，定义为小顶堆需要传入三个模板参数：

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> freq; for (int num : nums) freq[num]++; // 使用小顶堆，堆顶是最小频率 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (auto& [num, count] : freq) { pq.push({count, num}); if (pq.size() > k) { pq.pop(); } } vector<int> result(k); for (int i = k - 1; i >= 0; i--) { result[i] = pq.top().second; pq.pop(); } return result; } };

几个实现上的注意点：

• pair 的比较规则是先比 first，再比 second。小顶堆意味着频率小的在堆顶，符合“淘汰最小频率”的需求
• 遍历哈希表时，每插入一个元素就检查大小，超过 K 立刻弹出堆顶，确保堆永远只保留 K 个
• 最后结果数组要倒序填充，因为堆顶是第 K 大的，先弹出的是排名最靠后的元素

如果你用 Java 写，思路完全一样：先用 Map 统计，再定义 PriorityQueue 并自定义 Comparator，最后依次取出即可。原理层没有语言差异。

4.4 其他解法和适用场景

除了小顶堆，这道题还有两种常见解：

• 全排序：把哈希表转成 vector 按频率排序，取前 K 个。代码最简单，但 O(n log n) 在数据量大时不划算，适合 K 接近 n 的场景
• 基于快速排序的 partition 思想：类似求数组第 K 大的快选算法，平均复杂度 O(n)，但最坏情况退化到 O(n²)，工程上不如堆稳定

如果题目改成“前 K 个低频元素”，把小顶堆换成大顶堆即可，思路完全对称。如果改成“求出现频率第 K 大的元素”，同样是堆的经典应用。实际工作中处理 Top K 问题时，我优先用堆，因为复杂度稳定，而且不需要像 partition 那样在意输入分布。面试官如果追问为什么不用快速选择，可以从最坏复杂度、代码可维护性两个角度回答。

5. 实战心得与常见问题速查

5.1 三道题的共性规律

刷完这三道题，我最大的感受是：数据结构不是孤立的知识点，它们都是为算法服务的工具，而算法的本质永远是“减少无效计算”。

150 题用栈消除括号和优先级处理的复杂性。239 题用单调队列消除窗口内的重复比较。347 题用小顶堆把全排序降成局部排序。三题的优化思路是同一根主线：想清楚哪些信息是计算必须的，哪些是冗余的，然后选一个合适的数据结构让冗余信息快速淘汰。

这个思维模型远比记三道题的模板更值钱。面试题再怎么变，核心方法就那几个，能灵活组合才是真正的功力。比如“维护一个单调结构来减少比较”和“用堆只保留 Top K”，这两个方法论放到新的题里，往往就是破题的钥匙。

5.2 面试加问与变体思路

面试官很可能在这三道题上追加问题，我列几个高频追问和应对思路：

• 150 题：如果输入是中缀表达式怎么办？回答思路是先把中缀转后缀，用两个栈处理运算符优先级，再套用本题逻辑
• 150 题：能不能用递归实现？可以，但本质还是栈，递归栈也满足后进先出，只是可读性不如显式栈清晰
• 239 题：如果要维护滑动窗口的最小值，怎么改？把 push 中的大于号改成小于号，逻辑完全对称
• 239 题：K 等于 1 或等于数组长度时是否健壮？K=1 时窗口只有一个元素，直接返回原数组的拷贝；K 等于长度时单调队列退化为求整个数组的最大值，要能回答清楚
• 347 题：数据流动态更新时怎么维护前 K 个频率？答案是把固定数组改成实时更新的频率表和堆，涉及堆的调整逻辑，属于另一个层面了

这些问题基本都是同一道题换个角度，提前想一遍，面试时能省很多卡顿的时间。

5.3 刷题踩坑记录

最后分享几个我实际踩过的坑。

第一个坑：150 题里写减法和除法时 num1、num2 顺序搞反，这是新手大概率会遇到的问题。解决方式无非是刻意记一句“先弹出来的是右操作数”。

第二个坑：239 题里搞不清 pop 到底要不要判断值相等。我一开始简单粗暴地写成“窗口移动就 pop_front”，结果队首还没到离开的时候队列就空了。后来才彻底理解：push 时已经把更小的队尾淘汰了，所以移出窗口时只需要判断队首是否等于离开的元素。想明白这一刻，这道题才算真正过关。

第三个坑：347 题里直接对大顶堆调 top 取最大值，忽略了堆应该先维护成大小不超过 K。这样在极端输入下，比如大量元素频率相同，堆的维护策略不同会导致结果顺序有差异，虽然不影响最终集合的正确性，但调试时会有点困惑。

这三个坑有一个共同点：它们都不是算法方向选错了，而是对数据结构的边界行为理解不到位。把栈顶、队首、堆顶这些“临界位置”的行为想清楚，代码写出来自然就稳了。

如果你今天正好刷到这三道题，我的建议是别急着看题解，先拿单调队列那道题多琢磨一会儿。想明白“pop 为什么只要判断队首”的那一刻，比囫囵吞枣记十道题的模板都有用。后面再遇到类似的滑动窗口问题，你会发现脑子里已经有了一个成型的方法论，根据题目场景微调就能直接上手。