单调线性结构之 单调队列

简介

一个队列内部的元素具有严格单调性的一种数据结构，分为单调递增队列和单调递减队列。
1、维护区间最值；
2、去除冗杂状态；
3、保持队列单调（最大值是单调递减序列，最小值是单调递增序列）；
4、最优选择在队首。

思想

裸题

求所有长度为k的区间内的最大值

这种题的代码就是单调队列的模板了

1. 维护队首（对于上题就是如果你已经是当前的k个之前那你就可以被删了） ；
2. 在队尾插入（每插入一个就要从队尾开始往前去除冗杂状态） ；
3. 取出需要的最优解（队列头的值即是）；
4. 借助最优解，得到目前所求的最优解。

简单举例应用

数列为：6 4 10 10 8 6 4 2 12 14
N=10,K=3;
那么我们构造一个长度为3的单调递减队列：
首先，那6和它的位置0放入队列中，我们用(6,0)表示，每一步插入元素时队列中的元素如下
插入6：(6,0);
插入4：(6,0),(4,1);
插入10：(10,2);
插入第二个10，保留后面那个：(10,3);
插入8：(10,3),(8,4);
插入6：(10,3),(8,4),(6,5);
插入4，之前的10已经超出范围所以排掉：(8,4),(6,5),(4,6);
插入2，同理：(6,5),(4,6),(2,7);
插入12：(12,8);
插入14：(14,9);
那么f(i)就是第i步时队列当中的首元素：6,6,10,10,10,10,8,6,12,14

#include<bits/stdc++.h>
using namespace std;
int a[200000];
struct node
{
    int x,p;
    node(){}
    node(int xx,int pp){x=xx;p=pp;}
}list[200000];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int head=1,tail=1;
    list[1]=node(a[1],1);
    for(int i=2;i<=n;i++)
    {
        while(head<=tail&&list[tail].x<=a[i]) tail--;//删尾
        list[++tail]=node(a[i],i);//得到最优解并插入
        while(i-list[head].p>=m) head++;//去头
        if(i>=m) printf("%d\n",list[head]);
    }
    return 0;
}

例题

bzoj 1047 https://www.lydsy.com/JudgeOnline/problem.php?id=1047
洛谷 3088 https://www.luogu.org/problemnew/show/P3088