applications · 真实应用

应用实例：生产代码中的滑动窗口与单调队列

原理部分见各算法页，这一页先给出一个可动手体验的真实场景：数据像传感器读数一样逐个到达，要实时维护最近 k 个读数的最大值、最小值与极差（峰谷监控 / 告警）。用两个单调队列（一个递减维护 max、一个递增维护 min，机制见双端单调队列）就能把朴素的「每来一个数重扫 k 个」压到均摊 $O(1)$ 。

1 · 流式数据：最近 k 个读数的峰 / 谷 / 极差

两个队列各自每个下标只进出一次，所以处理整条流是 $O(n)$ 、每个新读数均摊 $O(1)$ ，而且不需要回看历史数据——这正是流式 (streaming) 处理需要的：数据来一个、处理一个，随时能给出当前窗口的 max/min/极差。朴素做法每来一个读数都要把窗内 k 个重扫一遍。

2 · 窗口的划分维度：count-based 与 time-based

上面那个 demo 的窗口是「最近 k 个读数」——按元素个数界定，这正是算法各页讲的 count-based 窗口。但工程里更常见的是「最近 N 秒」（Flink 聚合）、「now − T 内」（限流计数）这类 time-based 窗口：边界由时间而非个数界定。下面这条时间戳不均匀（有突发、有稀疏）的事件流，把两种窗口叠在同一时间轴上对照——同一批数据、同一时刻，一个固定时间、个数浮动，一个固定个数、时间浮动。

同一条流、同一个时刻：time 窗固定一段时间，窗内事件数随疏密起伏（突发时挤入很多、稀疏时可能只剩一个甚至落空）;count 窗固定 k 个事件，但它横跨的时间随疏密伸缩。两者机制同源——右进新值、左缩过期，只是「过期」的判据一个是「被挤出最近 k 个」、一个是「早于 now − T」。限流的滑动窗口日志、Flink 的最近 N 秒都是后者。

3 · 同一思路的其他应用场景

「维护一组还有希望胜出的候选，过期的从一端丢、被压制的从另一端丢」这套单调队列的方法，反复出现：

单调队列优化 DP

当 DP 转移形如 dp[i] = max(dp[j]) + w 且 j 落在一个随 i 滑动的窗口里（如「跳跃游戏 / 多重背包二进制拆分前的朴素式 / 有长度约束的最大子段」），就用单调队列维护这个窗口的最优 dp[j]，把每步的 $O(k)$ 取最值降到均摊 $O(1)$ ，整体从 $O(n\cdot k)$ → $O(n)$ 。

流式窗口聚合（Flink / 时序数据库）

实时计算引擎 (Flink、Spark Streaming) 与时序库 (Prometheus、InfluxDB) 大量做滑动窗口聚合：最近 N 秒的峰值 QPS、最大延迟、极差告警。定长窗口的 min/max 正适合单调队列——增量、低内存 ( $O(k)$ )、不重算历史。

API 限流的滑动窗口计数器 (rate limiter)

把单位时间 T 内的请求数限制在阈值内。固定窗口计数器 (fixed window) 每整段清零、实现最简，但相邻两段在边界处能叠出近两倍的瞬时流量。滑动窗口日志 (sliding window log) 给每个请求记一个时间戳，新请求到来时把窗口左界外（早于 $now - T$ ）的时间戳从队首逐个弹出，再看剩余数量是否超阈值——正是变长窗口「右进新值、左缩过期、队首淘汰」的形态。生产里常用 Redis ZSET 落地：ZADD 写时间戳、ZREMRANGEBYSCORE 删窗口外、ZCARD 取计数；Nginx limit_req、各类 API gateway 同源。

同源的 LeetCode 题

239 本题；把 $\ge$ 改 $\le$ 即滑动窗口最小值;1438「绝对差不超过 limit 的最长子数组」= 同时维护 max、min 两个单调队列；862「和 ≥ K 的最短子数组」= 在前缀和上跑单调队列。识别信号：「滑动窗口 + 取最值」。

静态区间最值：换成分块 / sparse table

如果窗口不定长、或要反复查任意区间的最值且数组不变，单调队列就不够了——改用分块法的近亲 sparse table: $O(n \log n)$ 预处理后任意区间最值 $O(1)$ 。要边改边查则上线段树。

可回到总览，或在双端单调队列页把队首输出、队尾淘汰的机制再单步走一遍——上面每个 case，拆开都是同一套「单调队列」动作。