cp-algorithms 数据结构：最小栈与最小队列的 O(1) 实现及滑动窗口最小值

文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载导读本文系统讲解如何在保持栈、队列原有渐近复杂度的前提下为它们增加 $O(1)$ 查询最小值的最小栈 / 最小队列能力并在此基础上解决经典的长度为 M 的滑动窗口最小值问题总复杂度 $O(n)$。读完本文你将掌握单调栈存储技巧、单调双端队列monotonic deque以及双栈模拟队列三种改造方案并能直接将其套用到 treap.md 中的 Cartesian Tree 构建、knapsack.md 中的单调队列背包优化等仓库内实际场景。1. 问题设定与整体思路本文围绕三个递进的问题展开与 src/data_structures/stack_queue_modification.md 保持一致改造栈使其能在 $O(1)$ 时间内查询栈内最小元素同时压入、弹出仍保持 $O(1)$对队列做同样的改造使其能在 $O(1)$ 时间查询队内最小元素利用上述结构在 $O(n)$ 时间内求出数组 $A$ 中所有长度为 $M$ 的连续子数组的最小值即滑动窗口最小值问题。之所以需要改造而不是另起炉灶是因为朴素的暴力方案无法同时满足插入/删除快与查询最小值快普通数组/链表可以 $O(1)$ 插入删除但求最小值需要 $O(n)$ 扫描预先维护全局最小值则无法处理弹出元素使最小值失效的情况。最小栈与最小队列的核心思想都是在元素入栈/入队时顺便维护当时窗口内的最小值把历史最小值随元素一起保存下来这样弹出元素时最小值信息仍然正确。2. 最小栈在每层栈底维护历史最小值2.1 核心思想栈的特点是只在同一端栈顶压入和弹出元素。因此可以做一个非常直接的改造不只在栈中存元素本身而是存一个二元组(元素值, 从该元素到栈底这段区间的最小值)stackpairint, int st;此时整个栈的最小值就等于st.top().second——因为栈顶元素的second字段记录的正是从栈顶一直往下到栈底的区间最小值而这个区间恰好覆盖了整个栈的全部元素。2.2 三种操作实现压入元素新元素入栈时栈的最小值要么是它自己空栈时要么是min(新元素, 原栈顶的 second)int new_min st.empty() ? new_elem : min(new_elem, st.top().second); st.push({new_elem, new_min});弹出元素直接弹出栈顶即可无需额外计算因为剩余栈顶元素的second字段依然准确int removed_element st.top().first; st.pop();查询最小值常数时间读取栈顶的secondint minimum st.top().second;压入、弹出、查询最小值三种操作全部是 $O(1)$空间占用为 $O(n)$每个元素多存一个int。这是一个在竞赛与工程中都极其常用的技巧很多单调栈问题的雏形正是这种栈内维护极值的写法。3. 最小队列方法一单调双端队列3.1 核心思想队列在两端操作尾端入队、头端出队无法像栈那样顺带维护到队底的最小值。方法一采用**单调队列monotonic queue**思路只保留那些未来可能成为最小值的元素。具体来说让队列中元素从头到尾保持非递减序最小值一定在队头入队时执行一次裁剪把队尾所有大于新元素的元素全部弹出再把新元素压入队尾。因为那些被弹出的元素既然比新元素大而新元素又比它们晚走新元素后入队、必然后出队它们在之后的任何时刻都不可能成为最小值删掉它们不会丢失最小值信息。出队时队头的元素可能早已在入队阶段被裁剪掉了。因此出队必须携带被删除元素的值只有当队头元素的值恰好等于被删除的值时才真正pop_front()否则说明该元素早已不在队列中什么也不做。dequeint q;查询最小值int minimum q.front();入队while (!q.empty() q.back() new_element) q.pop_back(); q.push_back(new_element);出队需要知道被删除元素的值remove_elementif (!q.empty() q.front() remove_element) q.pop_front();3.2 复杂度平摊amortized复杂度为 $O(1)$每个元素最多被压入一次、被弹出一次因此所有裁剪操作的总次数不超过 $O(n)$。这是滑动窗口问题最常用的实现方式。方法一的缺点是队列里并没有存储全部元素被裁剪掉的元素丢了因此出队时必须知道要删的是哪个值否则无法判断队头是否还有效。4. 最小队列方法二带索引的单调队列方法二是方法一的改进目的是支持不携带值即可删除队头元素。做法是给队列中的每个元素额外存一个入队序号同时记录已入队总数和已出队总数dequepairint, int q; int cnt_added 0; // 已入队元素总数 int cnt_removed 0; // 已出队元素总数查询最小值int minimum q.front().first;入队元素值 它自己的入队序号序号用于将来判断是否还有效while (!q.empty() q.back().first new_element) q.pop_back(); q.push_back({new_element, cnt_added}); cnt_added;出队每个元素在队列中的生命周期为[入队序号, 出队序号)。当一个元素应该出队时它的序号是cnt_removed。如果队头元素的序号恰好等于cnt_removed说明它还没有被裁剪掉需要真正弹出否则说明该元素早已被裁剪队头无需变动if (!q.empty() q.front().second cnt_removed) q.pop_front(); cnt_removed;这种序号判活的写法在滑动窗口类问题中非常实用因为窗口右端每次只推进一格出队的就是最早入队的那个元素其序号正好就是cnt_removed无需显式携带值。5. 最小队列方法三双栈模拟队列方法三的思路更巧妙用两个最小栈模拟队列从而复用第 2 节已经解决的问题并且这一次队列中确实存储了全部元素出队也无需知道值。5.1 双栈如何模拟队列新建两个最小栈s1、s2入队压入s1s1扮演队尾出队从s2弹出s2扮演队头翻转如果s2为空则把s1的所有元素依次弹出并压入s2。由于栈后进先出倒一趟就等价于把队头方向转到了s2的栈顶恰好还原了先进先出的顺序。stackpairint, int s1, s2;5.2 四种操作实现查询最小值整个队列 s1∪s2所以最小值就是两个栈最小值的较小者注意处理空栈if (s1.empty() || s2.empty()) minimum s1.empty() ? s2.top().second : s1.top().second; else minimum min(s1.top().second, s2.top().second);入队压入s1沿用最小栈的压入逻辑int minimum s1.empty() ? new_element : min(new_element, s1.top().second); s1.push({new_element, minimum});出队s2为空时先做一次整体翻转翻转过程本身也在维护s2的最小栈信息然后从s2栈顶弹出if (s2.empty()) { while (!s1.empty()) { int element s1.top().first; s1.pop(); int minimum s2.empty() ? element : min(element, s2.top().second); s2.push({element, minimum}); } } int remove_element s2.top().first; s2.pop();5.3 复杂度所有操作平摊 $O(1)$每个元素恰好经历压入 s1 → 转移到 s2 → 从 s2 弹出三次 O(1) 操作所以翻转的总代价分摊到每个元素上也是常数级。相比方法一/方法二方法三的优势是存储全部元素、且出队不依赖被删值但实现略复杂。6. 综合应用固定长度子数组的最小值滑动窗口最小值6.1 问题定义给定长度为 $N$ 的数组 $A$ 和长度 $M \le N$求所有长度为 $M$ 的连续子数组的最小值$$\min_{0 \le i \le M-1} A[i],\ \min_{1 \le i \le M} A[i],\ \min_{2 \le i \le M1} A[i],\ \dots,\ \min_{N-M \le i \le N-1} A[i]$$要求在 $O(n)$ 时间内完成。6.2 求解流程这是滑动窗口sliding window最经典的问法之一上面任意一种最小队列都可以直接解决流程完全一样先把数组前 $M$ 个元素依次入队此时队头就是第一个窗口的最小值输出然后重复入队下一个元素 → 出队窗口最前面的元素 → 队头即当前窗口最小值 → 输出直到窗口滑到数组末尾。因为每次入队、出队、取最小值都是平摊 $O(1)$整个过程只需遍历数组一遍总复杂度 $O(n)$且每个窗口只输出一次输出量本身也是 $O(n)$因此这是理论最优的线性算法。窗口丢弃最前面的元素这个动作正好对应三种方法各自的出队写法方法一需要知道被丢弃元素的值A[窗口左端]方法二直接调用出队内部用序号cnt_removed判断是否真正弹出方法三直接调用出队内部必要时翻转。7. 仓库中的实际应用印证最小栈/最小队列并非孤立知识点在本仓库的多个文档中都能找到它的直接应用Cartesian Tree 构建单调栈treap.md 在解决给定互异的 $(x_i, y_i)$ 构造笛卡尔树问题时明确指出该问题可用最小栈的改造在 $O(n)$ 时间内解决维护一个单调栈st对每个新节点弹出所有优先级更大的栈顶剩余栈顶即其候选父节点代码中的while(!st.empty() st.back()-prior it-prior) st.pop_back();与本文第 3 节的裁剪是同一思想。多重背包的单调队列优化单调队列knapsack.md 将多重背包的状态转移转化为最大值队列问题正是本文单调队列把换成即为最大队列的典型应用将多重背包优化到 $O(nW)$。仓库导航该主题位于 src/navigation.md 的Data structures分类下与 Segment Tree、Fenwick Tree 等并列属于数据结构基础章节。8. 三种方案对比与选型建议方案数据结构是否存储全部元素出队是否需要被删值实现复杂度平摊复杂度方法一单调队列dequeint否裁剪丢弃是最简单每操作 $O(1)$方法二带序号dequepairint,int否否简单每操作 $O(1)$方法三双栈模拟两个最小栈是否中等每操作 $O(1)$选型建议滑动窗口最小值窗口左端按顺序推进用方法一最直观配合数组下标即可需要无感删除、不想携带被删值时用方法二需要保留全部元素、或需要在同一种结构上既做栈又做队列语义时用方法三例如某些可撤销数据结构场景。把求最小值替换成求最大值只需把比较方向换成即可得到对称的最大栈 / 最大队列。9. 练习验证建议通过以下经典题目验证本文三种实现题目来源见 src/data_structures/stack_queue_modification.md 的 Practice Problems 一节Queries with Fixed LengthHackerRank给定查询长度求每个固定长度子数组的最小值直接套用第 6 节流程Sliding Window MinimumCSES编号 3221标准滑动窗口最小值模板题可分别用方法一与方法二各写一版对拍Binary LandCodeChefMAY20A/BINLAND将单调队列思想融入更复杂的网格/构造题场景。写完实现后可以手动构造边界用例自测全递增数组、全递减数组、重复值数组如[2,2,2]、长度 $M1$ 与 $MN$ 的极端窗口重点验证裁剪逻辑在处理重复值方法一、二用而非时的正确性以及方法三在s2空/非空交错时的翻转行为。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐cp-algorithms 稀疏表Sparse Table完全指南O(1) 区间最值查询的静态数据结构cp algorithms 稀疏表Sparse Table完全指南O 1 区间最值查询的静态数据结构 Sparse Table稀疏表是 cp algo文档教程知识库LeetCode 155. Min Stack 最小栈 Go 实现双栈法在常数时间内取最小值LeetCode 155. Min Stack 最小栈 Go 实现双栈法在常数时间内取最小值 导读 本文围绕 LeetCode 第 155 题 Min Sta示例工程滑动窗口最大值LeetCode 239双端队列维护单调队列的 O(N) 解法实战滑动窗口最大值LeetCode 239双端队列维护单调队列的 O N 解法实战 本篇技术指南以本仓库 problems/239.sliding windo文档教程知识库上一篇快速上手Python EXE解包揭开打包程序的神秘面纱下一篇如何使用HVM-lang进行主动安全测试终极指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考