题解：P1886 滑动窗口 /【模板】单调队列

· · 题解

本文摘自我的专栏：单调队列：实用而好写的数据结构。

2025.3.21 更新：修正了一处笔误，感谢 @Galaxy_Ivan 的贡献；将讲解部分求最大值改成了求最小值以匹配模板和题面；语言进行了些微润色，删除了部分冗余内容。

顾名思义，单调队列的重点分为「单调」和「队列」。

「单调」指的是元素的「规律」——递增（或递减）。

「队列」指的是元素只能从队头和队尾进行操作（实际上是个双端队列）。

—— OI Wiki

老生常谈的单调队列模板题了，题面要求定长区间最值，下面来说单调队列的运作方式（以求取区间最小值为例）。

单调队列的核心思想是：“老而更劣的元素永远不可能成为最值”（让我想起了我的 OI 生涯）。

例如：在从左往右滑动窗口求最小值时，考虑右侧新加入一个元素 a_j 时会发生什么。假设区间中已经有的一个元素 a_i 使得 a_i \ge a_j，那么 a_j 离开窗口一定比 a_i 要晚，且今后 a_i 在队列里的时候 a_j 也一直在队列里。在 a_i 剩下的生命里直到离开区间，a_j 永远比它小，a_i 再也不可能成为（唯一的）最小值了。

现实是残酷的，OIer 们是残忍的，a_i 已经失去了成为（唯一）最小值的机会，OIer 们毫不留情地抛弃掉它，来保证留下的都是有机会成为最小值的。

如此，单调队列保证了其中不存在 a_i,a_j 使 i<j 且 a_i \ge a_j，即对于任意 i<j 都有 a_i<a_j，换言之，这个单调队列里的元素是单调递增的。

总的来说，单调队列解决这道题（最小值部分）的过程分为两步：

  1. 加入新的元素时，从队尾踢掉之前所有不小于它的元素，并自己加入队尾
  2. 从队头移除已经离开窗口的元素

通常情况下上面两步顺序可以任意交换，少数情况下（即新加入的元素可能不在窗口内时）必须按照上面的顺序。对于这道题，顺序可以任意交换。每次完成上面两步以后，队头即为最小值。

附上我常用的模板代码（求定长区间最小值）：

int q[N],head,tail; //单调队列记录最小值的位置，方便后面判断某元素是否已经离开窗口
...
head=1,tail=0; //清空队列
for(int i=1;i<=n;i++) //枚举窗口右端
{
  while(head<=tail && i-q[head]+1>k) q[head++]=0; //弹出已经离开窗口的元素
  while(head<=tail && a[q[tail]]>a[i]) q[tail--]=0; //从队尾踢掉之前所有不小于当前元素的数
  q[++tail]=i; //当前元素自己加入队尾
  if(i>=k) res[i-k+1]=q[head]; //完成以上操作后，队头即为最小值
}

每个元素最多入队出队一次，所以时间复杂度是 O(n) 线性的。

对于这道题，同时要求最小和最大值。因为 \max(a_i) = - \min(-a_i)，即区间最大值等于序列相反数的最小值的相反数，所以我们可以只写一个求最小值的代码，求过区间最小值以后把序列所有元素取相反数再求一遍最小值，然后再取一次相反数就是区间最大值。

代码：

#include<cstdio>
using namespace std;

const int N=1e6+5;
int n,k,a[N];
int ans1[N],ans2[N];

int q[N],head,tail;
void Calc(int res[]) //指针传参，答案计入 res 数组
{
    head=1,tail=0; //清空队列
    for(int i=1;i<=n;i++) //枚举窗口右端
    {
      while(head<=tail && i-q[head]+1>k) q[head++]=0; //弹出已经离开窗口的元素
      while(head<=tail && a[q[tail]]>a[i]) q[tail--]=0; //从队尾踢掉之前所有比当前元素大的数
      q[++tail]=i; //当前元素自己加入队尾
      if(i>=k) res[i-k+1]=q[head]; //完成以上操作后，队头即为最小值
    }
    return;
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    Calc(ans1); //计算滑动窗口最小值位置，答案计入 ans1
    for(int i=1;i<=n-k+1;i++)
        printf("%d ",a[ans1[i]]);
    putchar('\n');

    for(int i=1;i<=n;i++)
        a[i]=-a[i]; //所有元素取相反数
    Calc(ans2); //计算此时的滑动窗口最小值位置，答案计入 ans2
    for(int i=1;i<=n-k+1;i++)
        printf("%d ",-a[ans2[i]]); //再取一遍相反数即为最大值
    return 0;
}

单调队列代码简短而好写，能够解决的问题范围清晰，是一种很实用的数据结构。未来可以发现，它的下限很低但上限也很高。单调队列不常作为一个裸的知识点来单独考，而是常常与动态规划等问题结合在一起，用作优化时间复杂度。

单调队列可以优化的问题具有以下特点：

同时，类似本题这种 “（连续移动的）定长区间最值问题”是单调队列中考得最多的一种，也是必须掌握的一种。

下面附上一份更加通用的单调队列模板（或者说其实算是伪代码？）：

定义/清空单调队列 //需要队头队尾均可压入和弹出，如双端队列
for(int i=1;i<=n;i++)
{
  while(队列非空 && 队尾劣于当前元素i) 弹出队尾;
  队尾压入i;
  while(队列非空 && 队头超出范围) 弹出队头;
  //此时队头为最优元素，按题目需要使用
}