跳转至

单调队列

✨ 引入

在学习单调队列前，让我们先来看一道例题。

滑动窗口的最值

📌 题意： 给定长度为 $n$ 的数组 ${a_i}$，窗口大小为 $k$，对于每个位置 $i$，求区间 $[i,\,i+k-1]$ 上的最大值。

🔒 约束： $n \le 10^6,\ 1 \le k \le n$

💡 最暴力的想法很简单，对于每一段 $i \sim i+k-1$ 的序列，逐个比较来找出最大值（和最小值），时间复杂度约为 $O(n \times k)$。

很显然，这其中进行了大量重复工作，除了开头 $k-1$ 个和结尾 $k-1$ 个数之外，每个数都进行了 $k$ 次比较，而题中 $100\%$ 的数据为 $n \le 10^6$，当 $k$ 稍大的情况下，显然会 TLE。

🎯 这时所用到的就是「单调队列」了。

🧐 介绍

单调队列 是一种特殊的双端队列，满足以下两个条件：

  • 🔁 支持从两端插入和删除元素（使用 deque 实现）
  • 📈 队列中元素始终保持单调递增或单调递减

📦 单调队列常用于处理如下问题：

  • 🪟 滑动窗口最大值 / 最小值
  • 🧩 动态维护某区间内最优解
  • 🔄 具有「滑动窗口」性质的问题

本节我们将以「滑动窗口最小值」问题为例，讲解单调队列的使用方式。

🧹 解题思路

🧱 单调队列的核心思想

队列保存 候选最小值，并保持队列内元素 单调递增。（从队头向队尾单调递曾）

对每个新元素 $a_i$，执行三步：

  • 🕒 过期判断：若队首索引 $< i-k+1$，则出队。
  • ❌ 剔除冗余：从队尾开始，将所有 $> a_i$ 的元素弹出。
  • ➕ 入队：将当前元素位置 $i$ 入队。

📊 操作过程示例

原序列为：1 3 -1 -3 5 3 6 7。

因为我们始终要维护队列保证其 递增 的特点，所以会有如下的事情发生：

操作 队列状态
$1$ 入队 {1}
$3$ 比 $1$ 大，$3$ 入队 {1 3}
$-1$ 比队列中所有元素小，所以清空队列 $-1$ 入队 {-1}
$-3$ 比队列中所有元素小，所以清空队列 $-3$ 入队 {-3}
$5$ 比 $-3$ 大，直接入队 {-3 5}
$3$ 比 $5$ 小，$5$ 出队，$3$ 入队 {-3 3}
$-3$ 已经在窗体外，所以 $-3$ 出队；$6$ 比 $3$ 大，$6$ 入队 {3 6}
$7$ 比 $6$ 大，$7$ 入队 {3 6 7}

🛠️ 具体实现

以维护最小值为例

维护一个双端队列 $q[1\ldots n]$，用两个指针 $h,t$ 表示当前队首、队尾：

  • $h=1,t=0$

当 $h>t$ 时，队列为空。

每步处理新元素 $a_i$（窗口大小 $k$）：

  • ${\bf 删除过期元素}$：若 $h\le t$ 且 $q_h<i-k+1$，则 $\text{h++}$.
    • 这意味着队头元素不可能是 $i$ 所在长度为 $k$ 的窗口内的最小值。
  • ${\bf 保持单调}$：当 $h\le t$ 且 $a_i< a_{q_t}$，则 $\text{t--}$.
    • 这意味着和 $i$ 有关的长度为 $k$ 的窗口，绝对轮不到 $a_{q_t}$ 当最小值。
  • ${\bf 入队}$：令 $\text{q[++t]=i}$.
  • ${\bf 输出答案}$：若 $i\ge k$，则当前窗口最小值为 $a_{q_h}$.

⏱️ 每个元素最多入队和出队一次，总复杂度为 $O(n)$。

int h = 1, t = 0;
for (int i = 1; i <= n; i++) 
{
    while (h <= t && i - q[h] + 1 > k) h++; // 队首和 i 的距离超过 k 队首离开
    while (h <= t && a[i] < a[q[t]]) t--; // 新的 a[i] 小于队尾，队尾则不可能成为最小值直接离开
    q[++t] = i;
    if (i >= k)
    {
        cout << a[q[h]] << " ";
    }
}

🧪 经典例题

🧮 例题一：最大连续和

🔢 题意： 给定长度为 $n$ 的数列 ${a_i}$ 和最大子段长度 $m$，求所有满足 $1\le j\leq i\le n$ 且 $i-j+1\le m$ 的非空子段的最大和：

\[ \max_{1\le j\le i,\;i-j+1\le m}(a_{j} + a_{j+1}+ a_{j+2} + \dots + a_i) \]

数据范围：$1 \le n \le 10^6$，$–10^9 \le a_i \le 10^9$，$1 \le m \le n$

📐 转化思路：

定义前缀和

\[ s_i = \sum_{j=1}^i a_j,\quad s_0=0 \]

则任意子段 $j\ldots i$ 的和为 $s_i - s_{j-1}$

因此题目可转化为

\[ \max(s_i-s_{j-1}),\ 1\le j\le i\le n,\ i-j+1\le m \]

即就是

\[ \max(s_i-s_j),\ 0\le j<i\le n,\ i-j\le m \]

此时可以枚举每个 $i$，即在 $i$ 之前找到一个 $j$ 满足 $1\leq i-j\leq m$ 且 $s_i-s_j$ 最大。

  • 枚举 $i$ 固定 $s_i$，若希望 $s_i-s_j$ 最大，则 $s_j$ 最小。

相当于在 滑动窗口 $[\,i-m,\,i-1]$ 上维护前缀和的最小值。

具体实现

  • 初始化：

    • $q[1] = 0,\quad h = 1,\; t = 1$
    • 初始将 $s_0$ 进行入队。因此初始化 $h=t=1$

  • 删除过期：

    • 队首元素 $q[h]$ 是否过期？
    • 若 $q[h] < i - m$， $\text{h++}$
  • 更新答案：
    • 对每个 $i$，在删除过期后：
    • $\mathrm{ans} = \max\bigl(\mathrm{ans},\;s_i - s_{q[h]}\bigr)$
  • 单调维护:
    • 如果当前前缀和更小，就把队尾较大的 剪掉：
    • 若 $h\le t$ 且 $s_i \le s_{q[t]}$，$t-1$
  • 入队当前下标:
    • $\text{q[++t] = i.}$

代码

// 初始化 h = t 保证队列有一个 0，即 s[0] 入队
int h = 1, t = 1, ans = -1e9;
for (int i = 1; i <= n; i++) 
{
    while (h <= t && i - q[h] > m) h++; 
    ans = max(ans, s[i] - s[q[h]]); // 入队之前更新答案防止空序列
    while (h <= t && s[i] < s[q[t]]) t--; 
    q[++t] = i;  
}

🐄 例题二：[USACO13NOV] Crowded Cows S

📌 题意：

有 $N$ 头奶牛 ($1\le N\le5\times10^4$)，第 $i$ 头奶牛位于一维坐标 $x_i$，身高 $h_i$。

如果在其 $\pm D$ 范围内（$1\le D\le10^9$）同时存在身高 $\ge2h_i$ 的左右两头奶牛，则它会觉得 拥挤。

求 觉得拥挤 的奶牛数量。

📈 策略

  • 首先预处理：
    • 将所有奶牛按 $x_i$ 从小到大排序，统一为 $(x_1,h_1),\dots,(x_N,h_N)$。

要判断第 $i$ 头牛左右两侧各有牛的身高 $\ge 2h_i$：

  • 左侧判断：维护一个窗口 $[\,x_i-D,\,x_i)$ 上的身高最大值 $\displaystyle M_L$。
    • 若 $M_L\ge2h_i$，则左侧成立。
  • 右侧判断：同理，对窗口 $(x_i,\,x_i+D]$ 维护最大值 $M_R$

$\Rightarrow$ 只需两次单调队列扫描，$\mathcal O(N)$ 时间。

具体实现：

左侧扫描：维护窗口最大身高

  • 使用双端队列 q 存储索引，队内对应的 $h$ 单调递减。
  • 扫描 $i=1\ldots N$：
    • 删除过期：队首索引 $q[h]$ 若满足 $x_i - x[q[h]] > D$，则出队。
    • 查询：若队非空且 队首身高 $\ge 2h_i$，则 $i$ 左侧成立（数组打标记）。
    • 入队前维护单调：当队尾索引 $i$ 满足 $h_i\geq h_{q[t]}$，则队尾出队。
    • 入队当前：$\text{q[++t] = i}$。

右侧扫描与统计答案

  • 对 $i=N\ldots1$ 倒序同样维护窗口 $(x_i, x_i+D]$，打上右侧的标记。
  • 最终答案：$\sum\limits_{i=1}^N [\,f[i]=1\land g[i]=1\,]$。
  • 具体实现可以借助结构体排序，整体时间复杂度为：$O(n\log{n})$。
int h = 1, t = 0;
for (int i = 1; i <= n; i++)
{
    while (h <= t && a[i].x - a[q[h]].x > d) h++;
    while (h <= t && a[i].y > a[q[t]].y) t--;
    q[++t] = i;
    if (a[q[h]].y >= a[i].y * 2) f[i] = 1;
}
h = 1, t = 0;
for (int i = n; i >= 1; i--)
{
    while (h <= t && a[q[h]].x - a[i].x > d) h++;
    while (h <= t && a[i].y > a[q[t]].y) t--;
    q[++t] = i;
    if (a[q[h]].y >= a[i].y * 2) g[i] = 1;
}

🟫 例题三：[HAOI2007] 理想的正方形

📐 题意：

给定一个 $a\times b$ 的整数组成矩阵，求所有 $n\times n$ 正方形子矩阵中

$\max(\text{区间值}) - \min(\text{区间值})$ 的最小值。

约束：$2\le a,b\le1000,\ 1\le n\le\min(a,b)$

🚫 暴力解法：

  • 枚举所有左上角 $(i,j)$（共 $(a-n+1)(b-n+1)$ 个），对应子矩阵大小 $n\times n$。
  • 内部再扫描 $n^2$ 个元素，求最大／最小。
  • 总时间：$\displaystyle O\bigl((a-n+1)(b-n+1)\times n^2\bigr)\approx O(abn^2)$，当 $a,b,n\sim10^3$ 时最坏 $10^{12}$ 次操作，必然超时。

🧮 二维单调队列：

  • 行方向预处理： 对每一行，用单调队列，

    • 计算该行上每个长度-$n$ 区间的 $\max,\min$，生成 两个矩阵 $\mathrm{rowMax}[i][j],\,\mathrm{rowMin}[i][j]$ （大小 $a\times (b-n+1)$）。

  • 列方向滑窗： 对每一列 $j\in[1,b-n+1]$，再用单调队列，

    • 在 $\mathrm{rowMax}[\ast][j]$ 上计算每个垂直区间的最大值$\max_{k=i}^{i+n-1}\mathrm{rowMax}[k][j]$，
      同理在 $\mathrm{rowMin}$ 上计算最小值。生成 两个矩阵 $\mathrm{colMax}[i][j],\,\mathrm{colMin}[i][j]$ （大小 $(a-n+1)\times (b-n+1)$）。

  • 对每个起点 $(i,j)$，取 $\Delta_{i,j}=\text{colMax}[i][j]-\text{colMin}[i][j]$，

  • 最后答案 $\min_{i,j}\Delta_{i,j}$。

📷 可视化图：

  • 使用单调队列求出每一行长度为 $n$ 的区间的最大值，如下所示。

    • xmx[i][j] 的值为原矩阵中所有 $1\times n$ 矩阵的最大值。

  • 在对 xmx 数组按照列做一遍单调队列，求出所有 $n\times 1$ 的最大值如下所示。
    • ymx[i][j] 的值为 xmx 矩阵中所有 $n\times 1$ 矩阵的最大值，而 xmx 矩阵的值又是原矩阵 A 中所有 $1\times n$ 矩阵的最大值，那么就相当于是原本矩阵中所有 $n\times n$ 的最大值。

代码

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e3 + 5;
int a, b, n, mat[N][N], xmx[N][N], ymx[N][N], q[N]; 
int xmn[N][N], ymn[N][N], ans = 2e9; 
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    cin >> a >> b >> n;
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            cin >> mat[i][j];
    for (int i = 1; i <= a; i++)
    {
        int h = 1, t = 0;
        for (int j = 1; j <= b; j++)
        {
            while (h <= t && q[h] < j - n + 1) h++;
            while (h <= t && mat[i][j] > mat[i][q[t]]) t--;
            q[++t] = j;
            if (j >= n)
            {
                xmx[i][j - n + 1] = mat[i][q[h]];   
            } 
        }
    }
    for (int j = 1; j <= b - n + 1; j++)
    {
        int h = 1, t = 0;
        for (int i = 1; i <= a; i++)
        {
            while (h <= t && q[h] < i - n + 1) h++;
            while (h <= t && xmx[i][j] > xmx[q[t]][j]) t--;
            q[++t] = i;
            if (i >= n)
            {
                ymx[i - n + 1][j] = xmx[q[h]][j];   
            } 
        }
    }

    for (int i = 1; i <= a; i++)
    {
        int h = 1, t = 0;
        for (int j = 1; j <= b; j++)
        {
            while (h <= t && q[h] < j - n + 1) h++;
            while (h <= t && mat[i][j] < mat[i][q[t]]) t--;
            q[++t] = j;
            if (j >= n)
            {
                xmn[i][j - n + 1] = mat[i][q[h]];   
            } 
        }
    }
    for (int j = 1; j <= b - n + 1; j++)
    {
        int h = 1, t = 0;
        for (int i = 1; i <= a; i++)
        {
            while (h <= t && q[h] < i - n + 1) h++;
            while (h <= t && xmn[i][j] < xmn[q[t]][j]) t--;
            q[++t] = i;
            if (i >= n)
            {
                ymn[i - n + 1][j] = xmn[q[h]][j];   
            } 
        }
    }
    for (int i = 1; i <= a - n + 1; i++)
    {
        for (int j = 1; j <= b - n + 1; j++)
        {
            ans = min(ans, ymx[i][j] - ymn[i][j]);
        }
    }
    cout << ans;
    return 0;
}

时间复杂度分析

  • 行预处理：每行 $\ O(b)$，共 $a$ 行，$O(ab)$。
  • 列滑窗：每列 $\ O(a)$，共 $b-n+1$ 列，$O(ab)$。
  • 总时间：$\boxed{O(ab)}$，可以处理 $10^6$ 量级数据。
  • 空间：额外存储两个 $a\times(b-n+1)$ 矩阵，$O(ab)$。