monotonic deque · 窗口最值

monotonic deque 与定长窗口

给定数组与窗口宽度 $k$ ，求每个长度为 $k$ 的连续窗口里的最大值。逐窗重扫要 $O(nk)$ ；相邻两个窗口只差一进一出，重扫把这份重叠全浪费了。

答案是把单调栈横过来用，得到的结构叫 monotonic deque：队列里存下标、对应的值从队首到队尾单调递减，队首恒为当前窗口的最大值。与单调栈相比只多一个动作：队首若已经滑出窗口，把它从前端赶走。这个结构因此不能只用栈，得是双端队列。

1 · 一步里的三件事

处理下标 $i$ 时依次做：

队尾淘汰：只要队尾的值不优于 $a[i]$ 就弹掉｜入队：把 $i$ 接到队尾｜队首过期：若队首下标 $\le i - k$ 就从前端弹掉

队尾淘汰的依据与单调栈一字不差：队尾那个元素比 $a[i]$ 小、又比 $a[i]$ 早进窗口，它此后每一个还包含它的窗口都同时包含 $a[i]$ ，它永远当不上最大值。队首过期则是定长窗口独有的：单调栈里的元素只会因为「有更强的后来者」而退场，队列里还多一种退场理由，就是「太老了」。

$a = [1, 3, -1, -3, 5, 3, 6, 7]$ 、 $k = 3$ 的完整轨迹：

$i$	0	1	2	3	4	5	6	7
队尾弹出	—	0	—	—	3, 2, 1	—	5, 4	6
队列内容	0	1	1, 2	1, 2, 3	4	4, 5	6	7
窗口最大值	—	—	3	3	5	5	6	7

图 1-1 · 单调队列的逐步维护。绿色是队首（当前窗口最值），红色是本步被弹掉的。可改窗口宽度与输入数组，并在最大值与最小值之间切换。

值得注意的是 $i = 4$ 那一步：一次弹掉三个下标。这与单调栈的情形一样，单步代价可以很高，而总代价被入队次数钉死。 $n = 10^5$ 的随机数组， $k = 100$ 时总操作数 199996， $k = 1000$ 时 199993，两者都紧贴 $2n$ ——窗口宽度根本不进入代价式。

2 · 队列长度的实测

队列的空间上界是 $k$ ：队里的下标都落在当前窗口内。但这个上界在随机数据上极度宽松。

$n = 10^5$ 、值域 $10^6$ 的随机数组实测： $k = 10$ 时队列平均长 2.93、峰值 9； $k = 100$ 时平均 5.18、峰值 17； $k = 1000$ 时平均 7.43、峰值 20。同一区间的 $\ln k + \gamma$ （ $\gamma \approx 0.5772$ 是 Euler–Mascheroni 常数）是 2.88、5.18、7.48。

三对数字贴得几乎逐位相同，这不是巧合。队列里存的是窗口内「从右往左的记录值」，也就是从当前位置往回看、依次刷新最大值的那些位置。随机排列中长度 $k$ 的前缀里记录值个数的期望正是调和数 $H_k = 1 + 1/2 + \dots + 1/k$ ，而 $H_k \approx \ln k + \gamma$ 。

图 2-1 · 队列长度分布与三种写法的结果互验。上方是队列长度的直方图与

H_k

参考线，下方并列单调队列、逐窗重扫与 sparse table 的答案。可调 n、k 与值域。

最坏情形仍然是 $k$ ：严格降序的输入里没有元素会被队尾淘汰，队列一路涨到窗口宽度。实测 $n = 10^5$ 的降序数组， $k = 100$ 时峰值就是 100， $k = 1000$ 时是 1000。

3 · 与本站相邻页的分工

滑动窗口系列从「窗口」这一侧看同一件事：它关心的是哪些聚合能增量维护（和、计数可以一减一加），而最值不能，于是引出这个结构。本页从「结构」这一侧看：单调队列是单调栈加一个过期淘汰，它的适用面不止于滑动窗口。

区间查询系列处理的是另一种查询模式。sparse table 允许任意区间、任意顺序、反复查询，代价是预处理。实测 $n = 20$ 万，sparse table 的表格子数是 3337875，即 $16.7n$ ；建表 9 到 14 ms，之后每次查询 $O(1)$ ，20 万次查询共 2 到 3 ms。单调队列建不了表，但它连一次预处理都不需要，同一组输入上 12 到 21 ms 跑完全程。

朴素逐窗重扫的实测是 42 到 47 ms，只比单调队列慢两到三倍，而名义上的差距是 $k = 500$ 倍。原因是朴素解法的内循环是一段没有分支预测失败、没有内存分配的紧凑数值比较，而单调队列每一步都要动一个 JS 数组。渐近复杂度描述的是增长速度，不是同规模下的绝对耗时：同一组数据把 $k$ 拉到 5000，朴素解法涨到 379 到 418 ms，单调队列仍是 14 到 17 ms，倍数这才从 2.2 到 2.5 拉开到 24 到 27。

4 · 参考文献

Knuth, D. E. (1997). The Art of Computer Programming, Vol. 1 (3rd ed., §2.2.1 Stacks, Queues, and Deques). Addison-Wesley.
LeetCode 239 · Sliding Window Maximum。本页 §1 轨迹表所用的输入即该题的样例。
Bentley, J. L. (1984). Programming pearls: Algorithm design techniques. Communications of the ACM, 27(9), 865–873. 滑动窗口与增量维护的早期系统论述。
Rényi, A. (1962). Théorie des éléments saillants d'une suite d'observations. 随机序列记录值个数的期望为 $H_k$ ，即本页 §2 的队列长度。