企业官网建设流程全解析

1. 先说结论：Day10 这四件事，到底在练什么

先把今天的内容框个范围。代码随想录Day10打卡，核心是三道题加一场梳理：150 逆波兰表达式求值、239 滑动窗口最大值、347 前 K 个高频元素，最后是栈与队列的总结。这三道题在 LeetCode 上分别对应中等、困难、中等，组合起来正好覆盖"栈"“队列”“单调队列”“优先队列”四个最重要的容器/数据结构考点，是面试里出现频率极高的一组题。

很多人刷到这一天会有个错觉：栈和队列不是挺简单的吗？一个先进后出，一个先进先出，有什么好练的。真正上手 239 和 347 的时候才会发现，难点从来不是"栈和队列怎么用"，而是"什么时候想到用它们""该维护什么信息""用哪种队列变体"。Day10 恰恰就是在解决这个"从会用到会用对"的跨越。

这篇笔记适合三类人：一是跟着刷题计划走、想系统复习数据结构的同学；二是准备面试、在短时间内过一遍高频题的人；三是刚学完栈和队列基础、想知道"这东西到底拿来干嘛"的初学者。我会把每道题的思路、代码、复杂度、易错点都拆开讲，最后再给一张对比表，方便你复习时直接看。

提前说一下，本文代码全部用 C++ 写，因为刷题场景下 C++ 的 STL 容器（stack、queue、deque、priority_queue）最接近底层实现，不容易被语言特性干扰思路。用 Java 的同学看思路完全没问题，容器名字大同小异。

2. 150. 逆波兰表达式求值：栈的"照妖镜"级应用

2.1 题目到底在说什么

逆波兰表达式也叫后缀表达式，核心特点是运算符写在操作数后面。比如我们习惯的中缀表达式(2 + 1) * 3，转成后缀就是["2","1","+","3","*"]。题目给的是一个字符串数组 tokens，每个元素要么是操作数，要么是运算符（+ - * /），要求算出最终结果。

为什么要把简单的四则运算搞成这副模样？因为后缀表达式对计算机极其友好：从头到尾扫一遍，不需要考虑括号、不需要运算符优先级，完全是线性处理。这个"线性处理"正是栈的舒适区。

2.2 为什么一看到这种题就该想到栈

想明白这个问题，比背代码重要得多。栈的核心特性是"后进先出"，天然适合处理"信息需要暂时囤积，等某个触发条件到来时再取出处理"的场景。

在逆波兰表达式中，我们遇到数字时并不知道它将来要和谁做运算，只能先存着；遇到运算符时，最近的、最后存进去的两个数字就是它的操作数。这个"最后存进去的先取出来"的过程，完完全全就是栈的 LIFO 行为。类比一下：一摞盘子，你总是先拿最上面那个，逆波兰表达式求值就是这个场景的数字化版本。

for (string& token : tokens) { if (token == "+" || token == "-" || token == "*" || token == "/") { long long second = st.top(); st.pop(); long long first = st.top(); st.pop(); // 运算结果压回栈顶，作为下一个运算符的操作数 } else { st.push(stoll(token)); } } return st.top();

注意一个细节：先出栈的second是右操作数，后出栈的first才是左操作数。减法first - second和除法first / second都有关顺序问题，写反了结果直接错。

2.3 完整代码与边界处理

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

这里说几个我在实际提交里踩过的坑：

第一，数字可能超出 int 范围。中间过程例如"10","6","9","3","+","-11","*","/","*","17","+","5","+"，算到17 * -11这类中间结果可能超过 int，所以栈里存long long。用stoll而不是stoi，也顺便避免了解析溢出问题。

第二，C++ 的除法向零取整，正好是题目要求的。-6 / 132 = 0，在 C++ 里(-6) / 132 = 0，符合题意。但如果用 Python 写，//是向下取整，负数场景会出现-6 // 132 = -1，必须特判改成int(a / b)。刷多语言的同学尤其注意这个差异。

第三，判断 token 是不是数字时，别用isdigit(token[0])。因为负数"-11"的第一个字符是'-'，会被误判成运算符。最稳的方式就是先把四种运算符精确匹配，剩下的都当数字处理。

2.4 这题的真正考点

做完后复盘，这道题表面考栈，实际考三件事：你会不会把"后进先出"翻译成逻辑；你知不知道表达式顺序；你懂不懂除法取整规则差异。前两点是栈的抽象建模能力，第三点是工程细节。面试时能把这三件事都讲清楚，比你闷头把代码默写出来强得多。

3. 239. 滑动窗口最大值：单调队列的第一次正面交锋

3.1 暴力法为什么挫败

题目要求：给定数组 nums，有一个大小为 k 的滑动窗口，每次右移一位，返回每个窗口的最大值。最直觉的写法是双重循环，外层窗口移动，内层遍历窗口找最大值，复杂度 O(n × k)。数据规模大一点就直接超时，因为窗口内有效信息完全没有被复用。

举个例子，窗口从[1, 3, -1]滑到[3, -1, -3]，旧窗口的最大值是 3，新窗口最大值还是 3，但暴力法会重新扫一遍3, -1, -3，把已经算过的信息丢掉。所以优化的核心思路就是：能不能让最大值的信息在窗口滑动时被"递推"出来。

3.2 单调队列：队头永远是答案

先说结论，这类"滑动窗口最值"问题的标准解法是单调队列，更准确地说是用双端队列 deque 维护一个单调递减的候选集。

队列里存的是元素下标，不是值。为什么要存下标？因为滑动窗口有"过期"概念，当队头下标小于i - k + 1时，说明这个元素已经离开窗口，必须被淘汰。只存值的话，你没法判断它是不是已经过期。

维护逻辑分两步：

• 入队时：从队尾开始，把所有小于等于当前元素的值弹出，再把当前下标压入队尾。这一步保证队列从队头到队尾是递减的，队头永远是当前窗口最大值的候选。
• 出队时：如果队头下标已经滑出窗口，弹出队头。

整个过程每个元素最多入队一次、出队一次，均摊复杂度 O(n)。这就是单调队列名字的来源：队列里所有元素单调，维护代价极小，取最大值只看队头，O(1)。

生活化类比：你维持一个"班级成绩排行榜"，新同学成绩进来时，比他低的同学已经没有机会当第一名了，直接删掉；成绩比他高的同学虽然暂时排前面，但可能会"毕业离队"，所以还得留在榜单里。最后榜单第一永远是我们关心的答案。

3.3 完整代码与逐行解读

class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> result; deque<int> dq; // 存下标 for (int i = 0; i < nums.size(); i++) { // 维护单调性：队尾小于等于当前值的弹出 while (!dq.empty() && nums[dq.back()] <= nums[i]) { dq.pop_back(); } dq.push_back(i); // 淘汰已经滑出窗口的队头 if (dq.front() <= i - k) { dq.pop_front(); } // 窗口形成后才开始记录结果 if (i >= k - 1) { result.push_back(nums[dq.front()]); } } return result; } };

几个细节值得交代：

• 出队条件为什么是dq.front() <= i - k而不是dq.front() < i - k + 1？因为二者数学上完全等价，但前一种写法不容易出错。i - k是"窗口左边界的前一个位置"，所以下标等于i - k的元素恰好是刚被移出窗口的那个，需要弹出。
• 压入新元素时用<=而不是<。假设窗口内有两个相等的值 5，旧 5 在队头、新 5 在后面，用<会把旧 5 留在队里，窗口滑动后旧 5 过期弹出新 5 顶上，逻辑也没错，但意味着队列里多存了一个"可能永远不会用到"的相等候选。用<=直接让新值覆盖旧值，队列更短，均摊性能相当，代码更干净。

这里的<=取舍值得你细品：它不会影响正确性，但体现了"单调队列要尽量让候选集紧凑"的设计思路。

3.4 为什么不能直接上大顶堆

有的同学会想，维护最大值不是可以用优先队列吗？大顶堆堆顶就是最大值，每次插入新元素、删除过期元素，取堆顶不就行了？

思路方向是对的，但实现上有坑：优先队列不支持 O(1) 地删除任意元素。你确实可以插入所有下标，靠"懒删除"跳过过期堆顶，但堆顶可能连续弹出多个过期元素，每弹一次 O(log n)，最坏情况下复杂度退化，而且内存占用 O(n)。面试时如果你说"我用堆 + 懒删除"，面试官大概率会追问"那你怎么处理堆顶过期？时间复杂度多少"，答不好就是送分变送命。

而单调队列因为维护的是"固定窗口内单调的候选集"，过期判断只需要看队头一次，这才是本题最优解。刷这道题的意义不在于背下单调队列模板，而在于体会"为了一个 O(1) 的队头答案，我们愿意牺牲一定空间和弹入弹出操作，换来整体线性复杂度"的权衡思路。

4. 347. 前 K 个高频元素：哈希表 + 优先队列的组合拳

4.1 题目拆解：统计和挑选是两步

题目给一个整数数组，要求返回出现频率最高的前 k 个元素。这题天然分两段：先用哈希表统计每个数字出现的次数，变成一堆(数字, 频率)对；再从这堆频率里选出最大的 k 个。

如果不知道这题在考什么，很多人的第一反应是：统计完直接按照频率排序，取前 k 个。排序法复杂度 O(n log n)，在数据量小时完全没问题，但面试官看的是你知不知道标准解法——维护一个大小为 k 的小顶堆，复杂度 O(n log k)。当 n 很大、k 很小的时候，O(n log k) 相比 O(n log n) 是明显的优化。

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

这是最反直觉的点。我们都想挑"最大"，直觉应该用大顶堆，对吗？但这里要挑的是"前 k 个最大的"，不是"每次取一个最大"。

用大顶堆的思路是把所有元素都装进堆，然后连续 pop k 次，每次 O(log n)，整体 O(n log n)。这本质上就是"用堆做全排序"，只不过排了一半，并没有利用 k 比较小这个优势。

用小顶堆的思路则完全不同：把堆的大小限制在 k，堆顶是堆里最小的那个元素。遍历所有 (数字, 频率) 对，如果当前频率比堆顶大，就把堆顶踢出去、把当前元素放进来。这样遍历完，堆里留下的自然就是频率最大的 k 个。堆顶在这里扮演的是"守门员"——它是当前前 k 名的门槛，但凡有更强的，先把最弱的踢了。

理解这个逻辑后你会发现，它和滑动窗口"淘汰过期/淘汰弱势候选"的思路是一致的：我们都是通过维护一个恒定的候选集，让候选集自动保留最有价值的信息。

4.3 完整代码与复杂度分析

class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { unordered_map<int, int> cnt; for (int num : nums) cnt[num]++; // 小顶堆，pair 按第一个元素（频率）排序 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (auto& [num, freq] : cnt) { pq.push({freq, num}); if (pq.size() > k) { pq.pop(); // 弹出频率最小的 } } vector<int> result; while (!pq.empty()) { result.push_back(pq.top().second); pq.pop(); } return result; } };

代码里的三行核心逻辑值得展开讲：

• priority_queue默认是大顶堆，这里用greater<>改变比较规则变成小顶堆。pair 比较时先比 first 再比 second，所以{freq, num}会按照频率升序排列，堆顶就是当前堆里频率最小的。
• 先 push 再判断pq.size() > k再 pop，比"先比较再决定是否 push"更简洁。堆大小只有 k，每次 push/pop 都是 O(log k)，总复杂度 O(n log k)。
• 最后输出时是"频率从小到大"的顺序，如果题目不要求顺序，可以直接返回；如果要求按频率从高到低，可以反转后再返回。

另一个容易忽略的问题是：如果数组中不同数字数量本身就小于 k，比如[1,1,2]且k=3，代码会正常返回所有数字，不会崩，因为限制pq.size() > k只在堆超过 k 时触发。

4.4 排序方案和小顶堆方案到底差在哪

做一个直观对比：

实际面试中，排序法可以作为"先给出可行解"的开场，然后主动说出"可以用大小为 k 的小顶堆优化到 O(n log k)"，这是很加分的节奏。同时也值得想一下：如果要求返回的频率顺序必须从高到低，堆内自然顺序是反的，可以先把堆倒到一个数组里再 reverse，没必要额外引入排序，复杂度仍是 O(k log k)，在 k 很小时可忽略。

5. 栈与队列全家桶总结：从数据结构到工程场景

5.1 栈、队列、单调队列、优先队列一张表记完

Day10 做完整理，我对四种"排队"类结构有了一个整体认识。这里给出一张浓缩的对比表，复习时直接照这个框架回忆就行。

记忆技巧：栈是"后到的先办事"，适合处理"嵌套"和"回溯"；队列是"先到的先办事"，适合处理"顺序"和"缓冲"；单调队列是"队列 + 淘汰机制"，适合"窗口"这种有时间限制的场景；优先队列是"队列 + 比较机制"，适合"只看最强/最弱"的场景。

5.2 三道题串成一条线的做题套路

做完 150、239、347 之后，我最大的体会是：这三道题的解题思路高度统一，都是在回答三个问题。

第一问：数据元素间的关系是什么？150 是"数字和运算符的先后关系"，239 是"窗口内元素的大小关系"，347 是"元素频率之间的比较关系"。

第二问：什么样的数据结构能高效表达这种关系？答案分别是栈、双端队列、优先队列。这不是分别背诵三个模板，而是同一个思维路径的三个出口：先抽象关系，再从工具集中找最匹配的容器。

第三问：代价是否可接受？150 的 O(n)、239 的均摊 O(n)、347 的 O(n log k)，都是"每个元素只处理常数/对数级次数"的规模。凡是你在题解里看到"单调""堆""栈"这些词时，最后都要自己补一句"时间复杂度为什么是这么多"，能答出来才说明真懂了。

还可以延伸一下：为什么这三题总被安排在一起？因为它们在结构上是递进的。150 是"后进先出"的启蒙；239 是"先进先出加淘汰"的进阶；347 是"按优先级淘汰"的高阶。从栈到单调队列再到堆，本质上是从"顺序"逐步走向"排序"，Day10 的精髓就在这条线上。

5.3 从刷题到工程：这些容器在真实世界里长什么样

面试里经常被追问"栈和队列在项目里有什么用"，这里随手列几个我实际遇到过的场景，帮你把数据结构概念和工程实践搭上桥。

栈在程序世界里最著名的存在是函数调用栈。每次调用函数，系统会把局部变量、返回地址、参数压栈；函数返回时再弹栈。递归爆栈、尾递归优化、调试工具的 backtrace 栈回溯，全都是栈的工程体现。理解"栈帧"这个词，就是理解"每一次函数调用对应一个栈帧，嵌套调用时栈帧层层叠加，返回时逆序释放"。

队列在工程里的延伸更广。消息队列（比如 Kafka、RabbitMQ、RocketMQ 这类消息中间件）虽然名字里带"队列"，实际干的事和数据结构队列不完全一样，它更多是"存储转发 + 削峰填谷 + 解耦"。你可以把消息队列理解成一个巨大的缓冲区：生产者把消息放进去，消费者按自己的节奏取出来，中间不需要上下游同时在线。线程池里的阻塞队列也是经典案例：任务提交线程往队列里放任务，工作线程从队列里取任务执行，当队列满或空时阻塞等待。这个场景的关键点和单调队列一样，都是"队列的容量管理决定系统的行为"，只是工程里多加了并发控制和背压机制。

把这些场景和刷题内容联系起来后，你会发现自己对"为什么栈和队列这么重要"的理解会深一个层次：它们不是抽象玩具，而是所有"异步""缓冲""上下文切换"类问题的底层原语。

6. 刷完这一天的笔记，我想多说几句

这天的内容比我预想的难，尤其是 239 的单调队列，我第一遍看题解时，只记住了"维护递减队列、队头是答案"这个模板，但为什么要存下标、为什么用<=弹出、为什么窗口过期只查队头，都是在手动模拟了两组数据之后才真正内化的。

我的建议是：这三道题不要只做一遍就完。第一遍求过得；第二遍合上题解自己写，卡住的地方就是你思维的盲区；第三遍尝试把每道题的"为什么用这个结构、复杂度为什么是这样"用几句话讲给别人听。能讲清楚，才算真的刷穿了。

另外一个很实用的小技巧：把这三题放在一起对比复习，而不是拆开刷完就忘。用记忆锚点的方式，比如"逆波兰 = 栈处理嵌套关系，滑动窗口 = 队列处理过期淘汰，前 K 高频 = 堆处理优先级淘汰"，一个场景对应一个数据结构，回忆时就像点菜一样，看到题目特征就能联想到工具。

如果你准备面试，建议在 150 上多练一下"运算符与操作数顺序"的细节，在 239 上多练一下"单调队列的入队出队条件"，在 347 上多练一下"小顶堆保留 k 个候选"的解释话术。这三个细节是面试官最爱追问的突破口，也是区分"背题"和"懂题"的关键。

最后再分享一个我自己的体会：栈和队列章节刷完之后，数据结构的基础就算真正立住了。后续的二叉树遍历（前中后序的递归转迭代就是栈）、图的最短路径（BFS 就是队列）、TOP K 系列（堆）全都要在这里打底。Day10 不是终点，反而是后面很多章节的最小依赖项，把这里吃透，后面的路会顺很多。