单调队列，洛谷P1886 滑动窗口_单调队列 洛谷

单调队列

我们都已经知道了队列是一种先进先出的结构，单调队列顾名思义就是一种递增或递减的队列。由于所用的元素各入队出队一次，所以它的时间复杂度是O(n)。

单调队列适用的范围

那么我们通常在什么情况下才会使用单调队列呢？
一般会在求一定范围内的最大值或最小值考虑单调队列，（当然线段树也可以在nlog(n)的时间内做到)

例题

下面我们以一个例题来讲解如何使用单调队列 洛谷P1886 滑动窗口 (点击可进入洛谷官网提交)。
题目大意：
有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
输入n,k,和序列a,其中n为序列a的大小，k为窗口大小。（1<=k<=n<=10⁶）
输出每次窗口滑动的最大值和最小值。

读懂题目意思我们很快就能想出一个暴力破解的思路，每次都枚举一个大小为k的区间，然后比出最大值，但是这样时间复杂度会高达O(nm)，妥妥的超时。

思路：
到了这里我们想是不是可以维护一个队列que（因为我们从前往后遍历a，满足先进先出的条件，考虑使用队列），que维护的内容为结构体，结构体的内容为元素的大小和下标，que.front()是对应窗口的最大值，我们遍历这个序列a，如果当前que的头部元素不在这个窗口所对应的范围内（即下标超界），那么就可以从que头部弹出该元素了(que.pop_front())，假设当前遍历到的元素a[i]，如果a[i]>=que.back(),那么说明a[i]比que.back()更有资格成为当前窗口的最大值，所以可以抛弃尾部元素了（que.pop_back()）,直到a[i]<que.back()，则将该元素加入que的尾部（que.push_back(a[i])），用while循环可以轻易实现这一步骤。到了这里我们就O(n)的时间内求出了所有的窗口最大值， 最小值也可以用同样的思路求出来，仔细观察一下que内部维护的值，我们发现它的元素的值满足单调递减的规律，所以它是一个单调队列。.

不多说了，直接上AC代码。

#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
const int maxn=2e6+286;
int st[2][2002000]; //用于存储答案

typedef struct node   //定义结构体用于存储元素的下标和大小
{
  int id,val;         //下标、大小
};  

node a[maxn];        //用于储存序列a

deque<node> que1,que2;  //que1维护最大值，即单调递减的队列（头部元素是最大值）
                        //que2维护最小值，即单调递增的队列（头部元素是最小值）
int main()
{
   
    int n,k;
    int cnt=0;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)     //读入序列a
    {
        scanf("%d",&a[i].val);
        a[i].id=i;
    }                 
    
    for(int i=1;i<=n;i++)     //遍历序列a
    {
        /*
        如果a[i]>=que.back(),那么说明a[i]比que.back()更有资格成为当前窗口的最大值，
        所以可以抛弃尾部元素了（que.pop_back()）
        */
         while(!que1.empty()&&a[i].val>=que1.back().val)  
              que1.pop_back();
              
        /*
        如果a[i]<=que.back(),那么说明a[i]比que.back()更有资格成为当前窗口的最小值，
        所以可以抛弃尾部元素了（que.pop_back()）
        */
         while(!que2.empty()&&a[i].val<=que2.back().val)
              que2.pop_back();
        
         que1.push_back(a[i]);  //将当前元素加入que
         que2.push_back(a[i]);
        
         while(i-k>=que1.front().id)
              que1.pop_front();    //当前维护的头部元素不在窗口的范围内，即下标越界了，删除头部元素
         while(i-k>=que2.front().id)
              que2.pop_front();
        if(i>=k)   //存储答案
        {
            st[1][++cnt]=que1.front().val;
            st[0][cnt]=que2.front().val;
        }
    }
    //输出答案
    for(int i=1;i<=cnt;i++)
        printf("%d ",st[0][i]);
    printf("\n");
    for(int i=1;i<=cnt;i++)
        printf("%d ",st[1][i]);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

希望在这里你能对单调队列有了进一步的了解，有所收获。
祝学习顺利！！！