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(vectorstring tokens) { stacklong 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: vectorint maxSlidingWindow(vectorint nums, int k) { vectorint result; dequeint 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: vectorint topKFrequent(vectorint nums, int k) { unordered_mapint, int cnt; for (int num : nums) cnt[num]; // 小顶堆pair 按第一个元素频率排序 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; for (auto [num, freq] : cnt) { pq.push({freq, num}); if (pq.size() k) { pq.pop(); // 弹出频率最小的 } } vectorint 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]且k3代码会正常返回所有数字不会崩因为限制pq.size() k只在堆超过 k 时触发。4.4 排序方案和小顶堆方案到底差在哪做一个直观对比方案时间复杂度空间复杂度适用场景全局排序O(n log n)O(n)n 较小、k 接近 n、代码最短大顶堆全量入堆O(n log n)O(n)思路直白面试不推荐小顶堆限制 kO(n log k)O(k)n 很大、k 很小标准解法实际面试中排序法可以作为先给出可行解的开场然后主动说出可以用大小为 k 的小顶堆优化到 O(n log k)这是很加分的节奏。同时也值得想一下如果要求返回的频率顺序必须从高到低堆内自然顺序是反的可以先把堆倒到一个数组里再 reverse没必要额外引入排序复杂度仍是 O(k log k)在 k 很小时可忽略。5. 栈与队列全家桶总结从数据结构到工程场景5.1 栈、队列、单调队列、优先队列一张表记完Day10 做完整理我对四种排队类结构有了一个整体认识。这里给出一张浓缩的对比表复习时直接照这个框架回忆就行。数据结构核心特性典型场景复杂度特征栈后进先出表达式求值、括号匹配、函数调用、回溯压栈弹栈 O(1)队列先进先出BFS、任务排队、缓冲入队出队 O(1)单调队列先进先出 内部元素单调滑动窗口最值、单调队列优化 DP均摊 O(1)优先队列按优先级出队TOP K、合并有序数组、贪心选优插入删除 O(log n)记忆技巧栈是后到的先办事适合处理嵌套和回溯队列是先到的先办事适合处理顺序和缓冲单调队列是队列 淘汰机制适合窗口这种有时间限制的场景优先队列是队列 比较机制适合只看最强/最弱的场景。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 不是终点反而是后面很多章节的最小依赖项把这里吃透后面的路会顺很多。