单调队列 —— 滑动窗口

dequeue双向队列

dequeue<int>que;//创建双向队列
que.push_front()//在队列前面塞一个元素
que.push_back()//在队列后面塞一个元素
que.pop_front()//删除队列第一个元素
que.pop_back()//删除队列的最后一个元素
que.clear()//清空队列
que.empty()//判断是否为空
que.size()//返回队列元素个数

单调队列

问题:

对每个长度为k的滑动窗体,求其最大值和最小值

思路1:

使出秘技dequeue (STL赛高!)

这里根据雨巨生动形象的例子,我来简单描述一下下:

题意:给出各届acmer的实力,众所周知大学基本上是四年,所以我们滑动窗口的大小就是4,问每个窗口中实力最强与最弱的是多少

举个样例:1 4 6 3 3 3 2

我们现在先求最大值,最小值在最大值的基础上改一改就行。

首先我们看给1入队列(是dequeue,后面不赘述),因为没到达四个元素,所以不输出,再到第二个元素4,大于1,说明在4的伟大作用下,1已经废了,就直接扔出去,也就是“去尾”,得到队列 4 。再到6,6 > 4,所以在6的存在下,4 废了,扔出去,得到队列 6。再到3,3 小于6,说明他有机会,因为可以等到6的退役了(也就是6滑出窗口了),他就可能是最大的,把 3塞进去,得到6,3的队列,现在达到窗口的大小,所以输出队头6,再看3,等于队列尾的元素,就把他也塞进去,再输出一个6,下一个3塞进来以后,我们判断发现队列头还没有出窗口,就再输出6,到了2,塞进去,发现6已经出了窗口,就得“去头”,所以输出3

总结一下,实现单调队列,主要分四个部分:

  • 去尾:队尾元素出队列。当有新的acmer等待入队时,需要从队尾开始判断会不会破坏队的单调性,会的话就去尾。
  • 入队:将新队员从队尾塞进来
  • 去头:队头元素出队列。当acmer满四年后就得退役,也就是要将其扔出队列
  • 取解:取队头元素
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef  long long ll ;
inline int IntRead(){//int的快读
    char ch = getchar();
    int s = 0, w = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') w = -1;
        ch = getchar();}
    while(ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();}
    return s * w;
}
int tr[MAX];
int main()
{
    int n, k;
    deque<int>q;//双向队列
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
    tr[i] = IntRead();
    for(int i = 1; i <= n; ++i){
        while (!q.empty() && tr[i] < tr[q.back()]) {
            q.pop_back();//去尾
        }
        q.push_back(i);//入队
        if(i >= k){//从第k个开始,后面都得输出
            while (!q.empty() && i - q.front() + 1 > k) {
                q.pop_front();//去头
            }
            if(i == k) cout<<tr[q.front()];//控制空格的输出
            else cout<<' '<<tr[q.front()];
        }
    }
    cout<<endl;
    q.clear();//清空队列
    for(int i = 1; i <= n; i++){
        while (!q.empty() && tr[q.back()] < tr[i]) {
            q.pop_back();
        }
        q.push_back(i);
        if(i >= k){
            while (!q.empty() && i - q.front() + 1 > k) {
                q.pop_front();
            }
            if(i == k)
                cout<<tr[q.front()];
            else
                cout<<' '<<tr[q.front()];
        }
    }
    cout<<endl;
}

思路2:

手写队列

head代表队列头,tail代表队列尾

结构体的q数组即为“双向队列”,其id用来记录下标,val来记录值

还是那四步,去尾入队去头取解。

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 5
typedef  long long ll ;
inline int IntRead(){//int的快读
    char ch = getchar();
    int s = 0, w = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') w = -1;
        ch = getchar();}
    while(ch >= '0' && ch <= '9'){
        s = s * 10 + ch - '0';
        ch = getchar();}
    return s * w;
}
int tr[MAX], n, k;
struct ran{
    int id, val;
}q[MAX];

void getmin(){
    int head = 1, tail = 0;//初始化
    for(int i = 1; i <= n; ++i){
        while (head <= tail && tr[i] < q[tail].val) tail--;//去尾
        q[++tail].id = i;//入队的时候记得要记录两部分
        q[tail].val = tr[i];
        while (i - q[head].id + 1 > k) head++;//去头
        if(i >= k){
            if(i == k)cout<<q[head].val;//控制空格,防止PE
            else cout<<' '<<q[head].val;
        }
    }
    cout<<endl;
}

void getmax(){
    int head = 1, tail = 0;
    for(int i = 1; i <= n; ++i){
        while (head <= tail && q[tail].val < tr[i]) tail--;
        q[++tail].id = i;
        q[tail].val = tr[i];
        while (i - q[head].id + 1 > k) head++;
        if(i >= k){
            if(i == k)cout<<q[head].val;
            else cout<<' '<<q[head].val;
        }
    }
    cout<<'\n';
}

int main()
{
    cin>>n>>k;
    for(int i = 1; i <= n; ++i) tr[i] = IntRead();
    getmin();
    getmax();
    return 0;
}

我看了一下这两个的时间差的不多,2ms,我感觉还是dequeue好写一些,嘎嘎,感觉写成函数更美观一点哎=(.)=

Tags: