单调队列

· · 算法·理论

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

一、定义与特性

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

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

二、典型应用场景

  1. 滑动窗口最值问题
    如LeetCode 239题，给定数组和窗口大小k，求每个窗口的最大值。单调队列通过以下步骤高效解决：

    • 插入时剔除比新元素小的队尾元素，保持单调递减性。
    • 删除超出窗口范围的队首元素，确保窗口有效性。
    • 队首即为当前窗口最大值，时间复杂度为O(n)。

  2. 动态规划优化
    在需要区间转移的DP问题中，单调队列可优化状态转移效率。例如：

    • 选择数字问题(洛谷P2034)：限制连续选择不超过k个数，求最大和。通过定义状态转移方程并维护单调队列，快速筛选最优前驱状态，将复杂度从O(nk)降至O(n)。
    • 最短子数组和问题(LeetCode 862)：求满Sum \geqslant k的最短子数组。通过前缀和数组结合单调队列，避免重复计算，高效定位可行解。

  3. 多维区间最值
    如处理矩阵中的n\times n子矩阵最值问题时，先对每行用单调队列求滑动窗口最值，再对结果矩阵的每列再次处理，最终得到全局最优解。

三、算法实现步骤

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

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

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

#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) 静态区间查询，多次询问

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