高效区间最值维护：单调队列的核心原理与实现指南

核心逻辑与数学原理

单调队列（Monotonic Queue）本质上是一种维护区间最值的数据结构。其核心思想是：如果在当前窗口中，一个老元素的生存时间（生命周期）比新元素短，且其值不如新元素优秀，那么该老元素将永远不可能成为区间最值。

对于求区间最大值问题，设当前窗口右端点为 $i$，左端点为 $ ext{max}(1, i-k+1)$。设队列中存储的是数组下标。对于队列中任意两个相邻的元素下标 $x$ 和 $y$（其中 $x$ 先于 $y$ 入队，即 $x < y$），必然满足：

$$A[x] ext{ ≥ } A[y]$$

当新元素 $A[i]$ 尝试入队时，为了保持队列的单调递减性，必须从队尾弹出所有满足 $A[ ext{tail}] < A[i]$ 的元素。

从时间复杂度来看，每个元素至多入队一次、出队一次。因此，即使内部存在 while 循环，其分摊时间复杂度（Amortized Time Complexity）严格为：

$$O(N)$$

空间复杂度为：

$$O(N)$$

状态设计与双端队列 std::deque 踩坑指南

1. 状态设计与双端队列操作

队列中不直接存储数组的值，而是存储数组的下标。因为下标既能提供值信息（通过 $A[ ext{index}]$ 索引），又能提供生命周期信息（通过 $i - ext{index} ext{ ≥ } k$ 判断是否过期）。

队头检查：若 $ ext{head extunderscore index} ext{ ≤ } i - k$，说明该元素已滑出窗口，执行队头出队。
队尾去劣：若当前元素 $A[i]$ 优于队尾元素，队尾不断出队，直到满足单调性或队列为空。
新入队：将当前下标 $i$ 推入队尾。
获取最值：队头对应的元素即为当前窗口的最值。

2. std::deque 踩坑指南

在 NOIP 竞赛等时限严苛的场景下，严禁直接使用标准模板库中的 std::deque。

内存碎片与常数巨大：std::deque 并非连续内存存储，而是分段连续的中央控制板结构。其内部指针重载、频繁的动态内存分配会导致巨大的常数开销。在 $10^6$ 数据量下，std::deque 的耗时通常是手写数组模拟队列的 $3$ 到 $5$ 倍，极易因卡常导致 TLE。
替代方案：必须使用原生数组模拟双端队列。用两个指针 head 和 tail 分别指向队头和队尾，操作均为 $O(1)$ 的指针移动，对 CPU 缓存极其友好。

C++ 标准源码（NOIP风格）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 1000005;
int a[MAXN];
int q[MAXN]; // 手写数组模拟双端队列，存储下标

int main() {
    // 优化标准输入输出流，加速 I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    if (!(cin >> n >> k)) return 0;

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    // 第一遍：求区间最小值
    int head = 1, tail = 0; // 初始化为空队列
    for (int i = 1; i <= n; ++i) {
        // 1. 队头合法性检查：剔除滑出窗口的元素
        if (head <= tail && q[head] <= i - k) {
            head++; 
        }
        // 2. 队尾单调性维护：若新元素更小，老元素永无出头之日
        while (head <= tail && a[q[tail]] >= a[i]) {
            tail--; // 致命点：必须是 >= 而非 >，相等的元素保留后者生存期更长
        }
        // 3. 当前元素下标入队
        q[++tail] = i;
        // 4. 窗口完整时输出答案
        if (i >= k) {
            cout << a[q[head]] << (i == n ? "" : " ");
        }
    }
    cout << "\n";

    // 第二遍：求区间最大值
    head = 1, tail = 0; 
    for (int i = 1; i <= n; ++i) {
        if (head <= tail && q[head] <= i - k) {
            head++;
        }
        while (head <= tail && a[q[tail]] <= a[i]) {
            tail--; // 维护单调递减，新元素大则剔除队尾
        }
        q[++tail] = i;
        if (i >= k) {
            cout << a[q[head]] << (i == n ? "" : " ");
        }
    }
    cout << "\n";

    return 0;
}

NOIP 实战避坑指南

1. 队列边界越界与死循环

在使用数组模拟队列时，while 循环条件中必须首先检查队列是否为空，即 head <= tail。

// 错误示范
while (a[q[tail]] >= a[i]) tail--;

若未加 head <= tail 限制，当输入序列单调递减（求最小值时）或单调递增时，tail 会不断自减变成负数，从而导致数组越界访问（RE）或因内存数据异常陷入死循环。

2. 窗口大小 $k > n$ 的极端边界情况

在部分变体题目中，窗口大小 $k$ 可能是动态变化的，或者初始 $k > n$。若不加控制直接执行 if (i >= k) 输出，会导致整个程序没有任何输出，在评测中直接爆零。代码中必须对 $k$ 与 $n$ 的大小关系进行边界判断，或者根据题目要求自适应调整有效窗口边界。

经典 NOIP/洛谷真题

1. 洛谷 P1886 滑动窗口 /【模板】单调队列

题意描述：给定一个长度为 $n$ 的数组和一个大小为 $k$ 的窗口。窗口从最左边滑到最右边，每次向右移动一个位置。求每次移动后窗口中的最大值和最小值。
问题本质：纯粹的静态区间最值维护。
核心解题思路：标准单调队列模板。两遍扫描，第一遍维护单调递增队列求最小值，第二遍维护单调递减队列求最大值。严格利用数组模拟，确保 $O(n)$ 复杂度卡满时限。

2. 洛谷 P2216 [HAOI2007] 理想正方形

题意描述：给定一个 $a imes b$ 的整数矩阵，要求从中找出一个 $n imes n$ 的正方形区域，使得该区域内的最大值与最小值的差最小。
问题本质：二维滑动窗口最值问题。
核心解题思路：二维单调队列。先对矩阵的每一行做一次一维滑动窗口（长度为 $n$），分别用单调队列求出每行各区间的最大值和最小值，结果存入辅助矩阵 $B$。接着，对辅助矩阵 $B$ 的每一列做一次一维滑动窗口（长度为 $n$）。通过两次一维单调队列的组合，在 $O(a imes b)$ 的时间复杂度内将二维最值问题彻底降维解决。