单调队列(数组deque)

优先队列:

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出(first in, largest out) 的行为特征。通常采用数据结构来实现。

单调队列: 单调递减或单调递增的队列,∈优先队列

deque方法:

void push_front(const T x)头部增加一个元素X
void push_back(const T x)尾部增加一个元素x
pop_front()删除双端队列中最前一个元素
pop_back()删除双端队列中最后一个元素

具体可看: [C++] deque容器简介

模板题: 滑动窗口

题干大意:

给一个长度为N的数组,一个长为K的滑动窗体从最左端移至最右端,你只能看到窗口中的K个数,每次窗体向右移动一位,你的任务是找出窗体在各个位置时的最大值和最小值。

思路: 求滑动区间max要构造单调递减队列,求min则要构造单调递增队列

队列变化(样例):

8 3
1 3 -1 -3 5 3 6 7
求min:队首-队尾 
1
1 3
-1
-3
-3 5
-3 3
-3 3 6
-3 3 6 7
求max:队首-队尾
1
3
3 -1
3 -1 -3
5
5 3
6
7

STL(deque)实现:

#includecstdio
#includealgorithm
#includedeque
#define foo(i,a,b) for(int i=a;i=b;i++)
using namespace std;
const int maxn=1e6+7;
int a[maxn];
int n,m;
int main(){
    scanf("%d%d",n,m);
    dequeint qmn,qmx;//队列存元素下标
    foo(i,1,n)scanf("%d",a+i);
    
    foo(i,1,n){
        while(!qmn.empty()i-qmn.front()=m) qmn.pop_front();//队首的元素如果超出范围,就把它删掉,注意要用while,= 
        while(!qmn.empty()a[qmn.back()]a[i]) qmn.pop_back();//保证队首最小 
        qmn.push_back(i);//向队尾加值
        if(i=m)printf("%d ",a[qmn.front()]);
    }//求区间最小值
    
    printf("\n");
    foo(i,1,n){
        while(!qmx.empty()i-qmx.front()=m) qmx.pop_front();
        while(!qmx.empty()a[qmx.back()]a[i]) qmx.pop_back();//保证队首最大 
        qmx.push_back(i);
        if(i=m)printf("%d ",a[qmx.front()]); 
    }//求区间最大值 
}

数组实现:

#includebits/stdc++.h
#define ll long long
const int manx=1e6+5;
ll q[manx],a[manx];
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    ll n,k;  cinnk;
    for(int i=1;i=n;i++) cina[i];//单调队列从1开始比较方便 
    
    ll tail=0,head=1;
    for(int i=1;i=n;i++){
        while(head=tailq[head]+k=i) ++head;//队首元素跟不上滑动窗口,所以移动头指针,注意= 
        while(head=taila[q[tail]]a[i]) --tail;//发现更小元素,更新 
        q[++tail]=i;//向队尾tail添值
        if(i=k) printf("%lld ",a[q[head]]);//q[head](队首)存最小
    }//求区间最小值
    
    printf("\n");
    tail=0,head=1;
    for(int i=1;i=n;i++){
        while(head=tailq[head]+k=i) ++head;
        while(head=taila[q[tail]]a[i]) --tail;
        q[++tail]=i;
        if(i=k) printf("%lld ",a[q[head]]);
    }//求区间最大值 
    return 0;
}
最新回复(0)
/jishuW_2BhVM1hyBPuvQQS20oKURC6VzNsOI3IhPKGbQA_3D_3D4794911
8 简首页