单调队列

单调队列是一种基于双端队列实现的高效数据结构，用于维护区间内的单调性，尤其适合处理滑动窗口最值问题。其核心思想是通过动态调整队列元素，确保队列内元素严格有序且满足特定窗口约束。以下从定义、应用场景及算法步骤三方面详细阐述：

一、定义与特性

单调队列是一种限制只能队尾插入，但允许两端删除的双端队列。队列内元素从队首到队尾呈严格单调性（递增或递减）。例如，维护最大值时队列为单调递减，最小值时为递增。其关键特性包括：

保序性：队列内元素的顺序与原序列严格一致，确保窗口覆盖范围的正确性。
高效操作：插入、删除、查询最值的时间复杂度均为 $O(1)$$($ 均摊分析 $)$ 。
下标存储：通常存储原序列的下标而非值，便于判断元素是否超出窗口范围。

例如，在滑动窗口最大值问题中，单调队列通过动态剔除冗余元素，始终保证队首为当前窗口最大值下标。

二、典型应用场景

滑动窗口最值问题
如 $LeetCode$ $239$ 题，给定数组和窗口大小 $k$ ，求每个窗口的最大值。单调队列通过以下步骤高效解决：
- 插入时剔除比新元素小的队尾元素，保持单调递减性。
- 删除超出窗口范围的队首元素，确保窗口有效性。
- 队首即为当前窗口最大值，时间复杂度为 $O(n)$ 。
动态规划优化
在需要区间转移的DP问题中，单调队列可优化状态转移效率。例如：
- 选择数字问题 $(洛谷P2034)$ ：限制连续选择不超过 $k$ 个数，求最大和。通过定义状态转移方程并维护单调队列，快速筛选最优前驱状态，将复杂度从 $O(nk)$ 降至 $O(n)$ 。
- 最短子数组和问题 $(LeetCode 862)$ ：求满 $Sum \geqslant k$ 的最短子数组。通过前缀和数组结合单调队列，避免重复计算，高效定位可行解。
多维区间最值
如处理矩阵中的 $n\times n$ 子矩阵最值问题时，先对每行用单调队列求滑动窗口最值，再对结果矩阵的每列再次处理，最终得到全局最优解。

三、算法实现步骤

以下以维护单调递减队列（求最大值）为例，说明核心步骤：

步骤	操作	时间复杂度
初始化队列	创建空双端队列，存储元素下标。	$O(1)$
维护队尾单调性	插入新元素i时，循环删除队尾所有对应值 $\leq$ 当前值的元素，保证队列递减。	均摊 $O(1)$
维护队首有效性	若队首元素下标超出当前窗口左边界（如 $i - front \geqslant k$ ），则删除队首元素。	$O(1)$
记录结果	当窗口完整形成（如 $i\geqslant k-1$ 时），队首元素即为当前窗口最大值。	O(1)

代码示例（滑动窗口最大值）：

CPP

#include <cstdio>
#include <deque>
using namespace std;

// 首先创建一个队列，并以第一个窗口中的元素进行初始化
deque<int> window;
for(int i = 0; i < k; ++ i) window.push_back(arr[i]);
// 每轮遍历队首元素出栈，并从队尾入队一个元素
for(int i = k; i < n - k + 1; ++ i)
{
    window.pop_front();
    window.push_back(arr[i]);
    // 查找当前队列中的最大值
    int max = window.front();
    for(int item : window) if(item > max) max = item;
    printf("%d ", max);
}

四、性能对比

方法	时间复杂度	空间复杂度	适用场景
暴力枚举	$O(nk)$	$O(1)$	小规模数据
单调队列	$O(n)$	$O(k)$	大规模数据，实时处理
线段树/ $ST$ 表	$O(n \log n)$	$O(n \log n)$	静态区间查询，多次询问

从表格可见，单调队列在动态窗口问题中具有显著优势，尤其适合处理数据流或实时性要求高的场景。

文章操作