算法与数据结构 / 单调栈与单调队列 · 弹出的那一刻定下答案 待审核 6 页

单调栈与单调队列 · 弹出的那一刻定下答案

一根柱子往右看，第一根比它高的在哪里？朴素写法对每根柱子各扫一遍右侧，最坏是 $O(n^2)$ 。monotonic stack 把这件事压成一遍扫描：栈里存下标、对应的值保持单调，新元素进来时把栈里所有「不如自己」的弹掉，而弹出的那一刻，被弹者要找的答案恰好就是新元素。整个技巧的来源只有这一句话，本系列后面每一页都是它的推论。

第一条线是结构本身。八个方向变体（next 与 prev 各四种，严格与非严格成对）其实只有四种弹栈判据，同一遍扫描读 next 就得到一组答案、读 prev 就得到另一组。把「弹出」换成「管辖区间」，就得到柱状图中最大矩形、最大全 1 子矩阵与子数组最小值之和；相等元素在这里埋着一个坑，两侧边界必须一严一松，否则贡献法要么重复计数要么漏计。第三页用势能法把「摊还 $O(n)$ 」这句话写成可验证的账本。

第二条线走向队列。定长窗口最值要的不是栈而是双端队列——与 monotonic stack 的差别只有一个动作：队首那个已经滑出窗口的元素要被淘汰。既然主角是 deque，就顺带看它自己怎么实现：ring buffer 一整块数组、满了搬家，分段数组一张 map 加固定块、扩张时一个元素都不搬。最后一页把这套结构能解的问题排开：接雨水的两种写法、股票跨度、去掉 k 位数字得最小、滑动窗口 median。

结构：弹出即定论

栈里的值保持单调，新元素把所有「不如自己」的弹出去。被弹的那个元素在此刻拿到答案，此后再也不被访问——每个元素进栈一次、出栈至多一次，总操作数不超过 $2n$ 。把答案换成「管辖区间」，一整类几何计数问题跟着落地。

monotonic stack · next greater

monotonic stack 的形状

栈里的值保持单调，新元素把所有不如自己的弹出去。被弹出的那一刻，被弹者要找的答案就是新元素——一整类「往左右找第一个更大或更小」的问题由此降到一遍扫描。

贡献法 · largest rectangle

管辖区间与贡献法

把「下一个更小元素」读成「作为最小值能管辖多宽」，柱状图最大矩形、最大全 1 子矩阵与子数组最小值之和就都落进一遍扫描。相等元素处的两侧边界必须一严一松。

摊还分析 · 势能法

摊还代价的势能账本

单调栈的单步代价可以达到 O(n)，总代价却是线性的。取「栈内元素数」当势函数，每一步的摊还代价恒为 2，这条等式在引擎的每组测试输入上都被逐项验过。

相等元素是唯一真正的坑

单调栈的代码只有七八行，写错的地方几乎总在同一处：弹栈条件用 > 还是 >=。求 next greater 时这两者只影响并列元素的答案指向，多数题目不在意；一旦进入贡献法就不同了——左右边界必须一严一松，否则同一条子数组会被两个相等的最小值同时认领（重复计数），或者两个都不认领（漏计）。实测长度 20 的全等数组：真值是 210，两边都严格给 1540，两边都非严格给 20（见管辖区间与贡献法 §3）。误差不是几个百分点，是数量级。含重复的随机数组上偏差小一些但同样系统性：长度 30、值域 4 的三组种子，两边都严格分别高出 47.5% / 25.0% / 13.9%。

单调栈与摊还分析 · 延伸阅读

All nearest smaller values — Wikipedia en.wikipedia.org 「每个元素左侧最近的更小值」这一问题的标准名字，含串行栈解法与并行算法，以及它在 Cartesian tree 构造中的用处。
摊还分析讲义 · Brown CS cs.brown.edu 聚合法、记账法、势能法三种手法。单调栈是势能法最干净的例题之一：势函数就取栈内元素数。
Stack-sortable permutation — Wikipedia en.wikipedia.org 一个栈能实现哪些排列、以及为什么答案是 Catalan 数。栈式扫描的组合学背景。
LeetCode 84 · Largest Rectangle in Histogram leetcode.com 柱状图最大矩形的题面与讨论区，管辖区间与贡献法 §2 的引擎按同一口径实现。

队列：多一个淘汰动作

定长窗口把「已经滑出去的元素」从队首赶走，其余与 monotonic stack 逐字相同。队首恒为窗口最值，于是 $O(nk)$ 的逐窗重扫降到一遍 $O(n)$ 。既然主角换成了 deque，也该看看它自己是怎么在两端都做到 $O(1)$ 的。

monotonic deque · 窗口最值

monotonic deque 与定长窗口

定长窗口的最值只比单调栈多一个动作：队首那个已经滑出窗口的元素要被淘汰。实测随机输入下队列平均只装 ln k + γ 个元素，远小于窗口宽度 k。

ring buffer · 分段数组

deque 本体的两种实现模型

单调队列的载体是 deque。ring buffer 用一整块数组、满了搬家；分段数组用一张 map 加固定块、扩张时一个元素都不搬。两者的取舍在引用稳定性与内存复用上。

窗口最值的三种写法怎么选

monotonic deque、sparse table、逐窗重扫，三者对同一组输入给出完全相同的答案，判据是查询模式而非渐近复杂度。 窗口宽度固定且只顺序滑过一遍——用 monotonic deque。一遍

O(n)

、额外空间只有队列本身，实测随机数据下队列平均只装

\ln k + \gamma

个元素。 区间任意、要反复查——用 sparse table。建表

O(n \log n)

、单次查询

O(1)

，代价是表格子数实测 16.7 倍于

n

（

n

= 20 万时 334 万格）。它不要求区间等宽，也不要求按顺序问。 只查几次——逐窗重扫就够了。

n

= 20 万、

k

= 500 时朴素扫描 42 到 44 ms、单调队列 12 到 21 ms，差距不到四倍；建一张 sparse table 单是建表就要 9 到 14 ms。渐近复杂度在小查询量下说了不算。

deque 的实现 · 延伸阅读

std::deque — cppreference cppreference.com 标准对 deque 的要求：两端插入删除均摊 $O(1)$ 、随机访问 $O(1)$ ，且两端插入不使已有元素的引用失效。最后一条正是分段实现存在的理由。
libstdc++ · stl_deque.h github.com map 加固定块的一手实现：_M_reallocate_map 的重建逻辑、_M_pop_front_aux 里块空即释放的那一行，以及块长的 512 字节口径。
Circular buffer — Wikipedia en.wikipedia.org ring buffer 的下标折算、满与空的区分手法，以及它与分段数组在引用稳定性上的差别。
Rust · VecDeque doc.rust-lang.org Rust 标准库选了 ring buffer 而非分段数组，文档里明确写了元素在扩容时会被移动——与 C++ 的选择正好相反。

落地：一整类问题

接雨水、股票跨度、字典序最小的删数、滑动窗口 median。它们的共同点是都要问「左右第一个比我大 / 小的在哪」，或者「窗口里的极值是谁」。同一个问题往往有双指针、堆、sparse table 几种写法，分工的判据不是复杂度而是查询模式。

接雨水 · 股票跨度 · 删数 · median

一整类问题的落地

接雨水、股票跨度、删 k 位得最小、滑动窗口 median。前三个都能读成「往左右找第一个更大或更小」，最后一个换成对顶堆——本页给出四题的解法与它们各自的替代写法。

应用与相邻结构 · 延伸阅读

LeetCode 42 · Trapping Rain Water leetcode.com 接雨水的题面。同一题在本站另有对撞双指针视角，见接雨水。
LeetCode 402 · Remove K Digits leetcode.com 删数使字典序最小。它是单调栈里少见的「栈内保持不减、且预算用完就停」的变体。
Range minimum query — Wikipedia en.wikipedia.org RMQ 的各种预处理方案：sparse table、分块、Cartesian tree 加 LCA 的线性预处理常数查询解。