精华内容
下载资源
问答
  • 单调队列deque
    2022-03-07 12:58:28

    有一个长为 nn 的序列 aa,以及一个大小为 kk 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。

    例如:

    The array is [1,3,-1,-3,5,3,6,7][1,3,−1,−3,5,3,6,7], and k = 3k=3。

    输入格式

    输入一共有两行,第一行有两个正整数 n,kn,k。 第二行 nn 个整数,表示序列 aa

    输出格式

    输出共两行,第一行为每次窗口滑动的最小值
    第二行为每次窗口滑动的最大值

    输入输出样例

    输入 #1复制

    8 3
    1 3 -1 -3 5 3 6 7

    输出 #1复制

    -1 -3 -3 -3 3 3
    3 3 5 5 6 7

    说明/提示

    【数据范围】
    对于 50\%50% 的数据,1 \le n \le 10^51≤n≤105;
    对于 100\%100% 的数据,1\le k \le n \le 10^61≤k≤n≤106,a_i \in [-2^{31},2^{31})ai​∈[−231,231)。

    #include<bits/stdc++.h>
    using namespace std;
    int n,k,t;
    const int maxn=1e6+5;
    int num[maxn];
    deque <int> a;//单调队列的实现依靠双向队列
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        cin>>n>>k;
        for(int i=0; i<n; i++)
            cin>>num[i];//读入
        t=0;//队头在num数组中的位置,指针
        for(int i=0; i<n; i++)
        {
            while(!a.empty()&&a.back()>=num[i]) a.pop_back();//不优,弹出
            a.push_back(num[i]);
            if(i-t>=k&&num[t]==a.front())
            {
                t++;
                a.pop_front();
    
            }
            if(i-t>=k&&num[t]!=a.front()) t++;//如果num的t在队列已经弹掉,就不用弹出
            if(i>=k-1)
                cout<<a.front()<<' ';//注意只在窗口完全进入后再输出
        }
        cout<<endl;
        a.clear();//清空队列,重新计算
        t=0;
        for(int i=0; i<n; i++)
        {
            while(!a.empty()&&a.back()<=num[i]) a.pop_back();
            a.push_back(num[i]);
            if(i-t>=k&&num[t]==a.front())
            {
                t++;
                a.pop_front();
    
            }
            if(i-t>=k&&num[t]!=a.front()) t++;
            if(i>=k-1)
                cout<<a.front()<<' ';
        }
        return 0;
    }
    
    #include<cstdio>
    #include<cstring>
    using namespace std; 
    
    struct Monotone_queue
    {
        static const int maxn=1000001;
        int n,k,a[maxn];
        int q[maxn],head,tail,p[maxn];//同题目叙述一样,q是单调队列,p是对应编号。
        
        void read()
        {
            scanf("%d %d",&n,&k);
            for(int i=1;i<=n;++i)
                scanf("%d",&a[i]);
        }//读入不必说了
        
        void monotone_max()//单调最大值
        {
            head=1;
            tail=0;
            for(int i=1;i<=n;++i)
            {
                while(head<=tail&&q[tail]<=a[i])
                    tail--;
                q[++tail]=a[i];
                p[tail]=i;
                while(p[head]<=i-k)
                    head++;
                if(i>=k)printf("%d ",q[head]);
            }
            printf("\n");
        }
        
        void monotone_min()
        {
            head=1;
            tail=0;//为啥要这样呢?因为head要严格对应首元素,tail要严格对应尾元素,所以当tail>=head时,说明有元素。而一开始队列为空,说一要这样赋值。其实这跟普通队列一样。
            for(int i=1;i<=n;++i)
            {//a[i]表示当前要处理的值
                while(head<=tail&&q[tail]>=a[i])
                    tail--;//只要队列里有元素,并且尾元素比待处理值大,即表示尾元素已经不可能出场,所以出队。直到尾元素小于待处理值,满足"单调"。
                q[++tail]=a[i];//待处理值入队。
                p[tail]=i;//同时存下其编号
                while(p[head]<=i-k)
                    head++;//如果队首元素已经"过时",出队。
                if(i>=k)printf("%d ",q[head]);//输出最值,即队首元素。i>=k表示该输出,至于why就自己看题目。
            }
            printf("\n");
            
        }
    }worker;
    
    int main()
    {
        worker.read();
        worker.monotone_min();
        worker.monotone_max();
        return 0;
    }

    更多相关内容
  • // hh和tt存放的是队列的首尾指针 for(int i=0;i<n;++i){ if(hh<=tt&&i+1-q[hh]>k) ++hh; while(hh<=tt&&nums[q[tt]]>=nums[i]) --tt; ...
  • 单调队列

    目录

    算法解析

    1.什么是单调队列

    2.优势

    3.单调队列适用于那些范围

    4.两个应用

    5.队列常用操作

    例题:



    算法解析

    1.什么是单调队列

    顾名思义,就是兼具单调性质队列性质的数据结构

    2.优势

    如果我们想在一个普通队列中找到一个极值,需要遍历整个队列,时间复杂度为线性O(N)

    单调队列因为具有单调性,只需要调用队首或者队尾,时间复杂度为常数O(1)

    3.单调队列适用于那些范围

    单调队列,其实是单调栈的一个升级plus版本,或者说是具有[l,r]区间性质的单调栈.(注:单调栈一般来说是[0,r]类型的)

    4.两个应用

    (1)求窗口(区间)的极值
    (2)求离一个元素最近的比它小的或者比他大的元素

    5.队列常用操作

    (1)queue<int> q;

    q.clear();        q.pop();        q.front();        q.back();        q.size();        q.empty();

    (2)deque<int> q;

    q.push_back();        q.push(_front);        q.pop_front();        q.pop_back();       

    q.size();        q.empty();        q.clear();

    参考:[投稿]2019年4月11日单调队列讲义 - AcWing


    例题:

    154. 滑动窗口 - AcWing题库

    解法一: deque双端队列

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e6 + 7;
    
    int n, k;   
    int a[N];   //原数组
    int q[N];   //模拟队列,保存下标
    
    int main()
    {
        cin >> n >> k;
        for(int i = 0; i < n; i ++ )
            cin >> a[i];
            
        int hh = 0, tt = -1;    //head, tail; tail设为-1表示队列为空,没有元素    
        for(int i = 0; i < n; i ++ )    //找极小值
        {
            while(hh <= tt && q[hh] < i - k + 1) hh ++ ;    //范围大于K
            while(hh <= tt && a[i] <= a[q[tt]])  tt -- ;
            //while不要忘记加上判断队列是否为空        
            q[++ tt] = i;
            if(i - k + 1 >= 0)   cout << a[q[hh]] << " ";    //不要输出q[hh]
        }
        
        cout << endl;
        
        //这里不需要重置队列,只需要重置下标
        hh = 0, tt = -1;
        for(int i = 0; i < n; i ++ )
        {
            while(hh <= tt && q[hh] < i - k + 1)    hh ++ ;
            while(hh <= tt && a[i] >= a[q[tt]]) tt -- ;
            q[++ tt] = i;
            if(i - k + 1 >= 0)   cout << a[q[hh]] << " ";
        }
        
        cout << endl;
        return 0;
    }

    解法二 :数组模拟单调队列

    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e6 + 7;
    
    int n, k;   
    int a[N];   //原数组
    int q[N];   //模拟队列,保存下标
    
    int main()
    {
        cin >> n >> k;
        for(int i = 0; i < n; i ++ )
            cin >> a[i];
            
        int hh = 0, tt = -1;    //head, tail; tail设为-1表示队列为空,没有元素    
        for(int i = 0; i < n; i ++ )    //找极小值
        {
            while(hh <= tt && q[hh] < i - k + 1) hh ++ ;    //范围大于K
            while(hh <= tt && a[i] <= a[q[tt]])  tt -- ;
            //while不要忘记加上判断队列是否为空        
            q[++ tt] = i;
            if(i - k + 1 >= 0)  //if(i - k + 1)会多输出,因为i-k+1可能为负数,但负数也为真
                cout << a[q[hh]] << " ";    //不要输出q[hh],q是存的数组a的下标
        }
        
        cout << endl;
        
        //这里不需要重置队列,只需要重置下标
        hh = 0, tt = -1;
        for(int i = 0; i < n; i ++ )
        {
            while(hh <= tt && q[hh] < i - k + 1)    hh ++ ;
            while(hh <= tt && a[i] >= a[q[tt]]) tt -- ;
            q[++ tt] = i;
            if(i - k + 1 >= 0)   cout << a[q[hh]] << " ";
        }
        
        cout << endl;
        return 0;
    }

    例题:134. 双端队列 - AcWing题库

    展开全文
  • 浅谈单调队列deque

    2019-08-18 23:42:37
    全部按单调队列加入的方式加入队列(从队尾加,不明白的可以再阅读一下上面讲述裸的单调队列的文字) ,然后统一将距离大于最大跳跃距离的节点删去(从队头开始删,直到删到距离小于最大跳跃距离的节点)。 做完这...

    引入

    引入问题(P1440):洛谷题面链接

    题目描述
    一个含有n项的数列(n<=2000000),求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始,若前面没有数则输出0。

    输入格式
    第一行两个数n,m。

    第二行,n个正整数,为所给定的数列。

    输出格式
    n行,第i行的一个数ai,为所求序列中第i个数前m个数的最小值。

    输入输出样例
    输入

    6 2 
    7 8 1 4 3 2
    

    输出

    0
    7
    7
    1
    1
    3 
    

    大致思路

    在没学单调队列以前,很多人(包括我)都会想到用队列去模拟,进一个节点,往前扫M个元素,然后输出,时间复杂度为O(N2),但我们一看数据就傻眼了:

    m≤n≤2000000
    

    肯定得爆炸!

    那我们怎么办呢?
    接下来引入单调队列——

    将一个节点压入队列,这时分两种情况:
    (1)队列为空,直接加入
    (2)队列不为空,比较队尾节点与该节点的大小,如果该节点比队尾节点要小(按照题意,让我们找最小的,如果是要找最大的,那就正好相反),就将队尾节点弹出,直到队列为空或者队尾节点比该节点小,将该节点插入;
    在加入节点时还要判断该队列长度是否超过M如果加入新节点后长度超过M,就将队头弹出
    总结一下:
    弹出节点的情况有:
    1.加入新节点时,新节点比该队列队尾要小(对于该题目),将队尾弹出;
    2.队尾位置-队头位置大于M,将对头弹出;
    加入节点的情况有:
    1.新节点大于(对于该题目)队尾;
    2.队列为空;

    如果您还没有听懂本蒟蒻的解释,那就请仔细阅读下面的样例分析
    全部节点:7 8 1 4 3 2
    第一轮循环:
    先输出0,因为此时队列为空;
    将7入队,因为此时队列为空;
    第二轮循环:
    先输出7,因为队头为7;
    将8,入队,放在7的后面,因为8>7;
    第三轮循环:
    先输出7,因为队头是7,同时队头7的位置和队尾8的位置差等于M,队头不需要删;
    将1入队,将7,8出队,因为1小于7和8;
    第四轮循环:
    先输出1,因为队头是1;
    将4放在队尾,因为4小于1;
    第五轮循环:
    先输出1,因为队头是1;
    将3入队,弹出4,因为4大于3;
    第六轮循环:
    先将1弹出,以为队列再加节点就超出边界了;
    输出3,因为3位于队头;
    将2入队,将3弹出;

    这里大家可能会有一个疑问:为什么2不输出来了呢?
    不理解的大佬可以仔细阅读一下这句话:序列中第i个数前m个数的最小值。(特别注意“”)

    算法构思

    设计队列
    这里的队列明显是一个结构体,里面有两个元素,一个存储节点位置,另一个存储节点的值。
    代码:

    struct Unsigned{
    	unsigned long long int Num;//存储位置 
    	unsigned long long int Data;//存储值 
    }Queue[9999999];//单调队列 
    //根据题意,队头为最小值,队尾为最大值 
    

    输入:注意用scanf或者快读,cin会爆。

    队列操作
    先判断队列是否为空,为空直接输出0;
    不为空就判断对列是否超限,超限删队头节点,将对头直接输出,不超限直接输出队头;
    然后是加入节点,按“大致思路”去删节点,再加入新节点。
    代码:

    for(register int i=1;i<=N;i++){
    	if((i-Queue[Front].Num)>M)
    		Front++;
    	//队尾位置-队头位置大于M,将对头弹出
    	printf("%lld\n",Queue[Front].Data);//输出最小值
    	while(Num[i]<Queue[Back].Data&&Front<=Back)
    		Back--;
    	//新节点比该队列队尾要小(对于该题目),将队尾弹出
    	//这个操作包括了对队列是否空的判断
    	Queue[++Back].Data=Num[i];
    	Queue[Back].Num=i;//加入节点
    }
    

    算法就完美结束了;

    总代码:

    #include "bits/stdc++.h"
    using namespace std;
    
    long long int N,M,Num[9900000];
    long long int Front,Back;
    
    struct Unsigned{
    	long long int Data;
    	long long int Num;
    }Queue[9900000];
    
    int main(void){
    	scanf("%lld%lld",&N,&M);
    	for(register int i=1;i<=N;i++)
    		scanf("%lld",&Num[i]);
    	//cin会炸
    	Front=1,Back=0;
    	for(register int i=1;i<=N;i++){
    		if((i-Queue[Front].Num)>M)
    			Front++;
    		printf("%lld\n",Queue[Front].Data);
    		while(Num[i]<Queue[Back].Data&&Front<=Back)
    			Back--;
    		Queue[++Back].Data=Num[i];
    		Queue[Back].Num=i;
    	}
    	cout<<endl;
        return 0;
    }
    

    小节

    大家会发现,这样做的算法的时间复杂度为O(N),完美通过测试。
    关于单调队列模板的题,这里再推荐两道: P1886滑动窗口P2032扫描
    其实NOIP几乎是不会裸考单调队列的,单调队列的主要功能是优化DP动态规划
    接下来将仔细讲解NOIP2017普及组第四题跳房子

    DP与单调队列例题

    洛谷题面链接

    大致思路:

    要是我考NOIP2017会GG的
    (1)金币的枚举
    这里我们用二分法,Right为1到最远的格子的距离(有人直接赋值10005,也是可以的),Left即为零,每次枚举出的所花金币书传入到一个bool函数Judge里,Judge判断这种方法是否可行,可行就弹出true,不可行就弹出false
    main函数的设计如下:

    int main(void){
    	scanf("%d%d%d",&N,&Jump,&Want);
    	for(register int i=1;i<=N;i++)
    		scanf("%lld%lld",&Where[i],&Num[i]);
    	//读入 
    	Left=0,Right=Where[N];//价值最少,价值最多 
    	while(Left<=Right){
    		Middle=(Left+Right)/2;//枚举的金币数 
    		if(DP_Judge(Middle)==true){//可行 
    			ACanswer=Middle;//记录 
    			Right=Middle-1;
    		}else{Left=Middle+1;}//不可行 
    	}
    	printf("%lld\n",ACanswer);
        return 0;//输出 
    }
    

    (2)Judge函数的设计
    我们先不考虑使用单调队列:
    设i>j,并且i,j两个格子的距离在跳跃范围以内,那么第i个格子有可能是由第j个格子跳过来的,所以第i个格子的值必然需要调用第j个格子,DP因此而生:
    设DP[i]表示跳到第i个格子的最大得分
    DP[i]的值取决于它自身(之前可能跳到过)和跳到它的格子的值
    于是方程就出来了:
    DP[i]=max(DP[i],DP[j]+V[j]);
    V[j]表示第j个格子自身的值;
    DP[j]表示跳到第j个格子的值得总和;
    不加单调队列优化的Judge设计如下:

    bool DP_Judge(int M){
    	Min=Jump-M;Max=Jump+M;
    	//Min为可跳的最小值
    	//Max为可跳的最大值 
    	if(Min<=0)Min=1;
    	//如果Min小于1,改为1(根据题意) 
    	for(register int i=1;i<=N+100000;i++)
    		DP[i]=-INF;
    	//因为某些格的分数出现负数 
    	DP[0]=0;//最开始肯定为0 
    	for(register int i=1;i<=N;i++){//扫所有格 
    		for(register int j=i-1;j>=0;j--){//扫能到达第i个格子的格子 
    			if(Where[i]-Where[j]<Min)continue;//如果太小,跳过 
    			else if(Where[i]-Where[j]>Max)break;//如果跳的范围超限,弹出 
    			DP[i]=max(DP[i],DP[j]+Num[j]);//方程 
    			if(DP[i]>=Want)return true;//超过了分数,达到了要求,弹出 
    		}
    	}
    	return false;//无法达到 
    }
    

    (3)单调队列及其优化(重点)
    我们先考虑这样一个问题:在DP[j]中找到一个最大的值,且第i个格子,第j个格子的距离在跳跃范围以内,j的范围是0<=j<i。

    解决了这个问题,就能优化我们的DP程序。

    我们刚才的方法其实只是暴力做这个问题,学了单调队列后,我们就能很轻松地解决这个问题:

    我们先将距离现在节点距离不小于最小跳跃距离的节点全部按单调队列加入的方式加入队列(从队尾加,不明白的可以再阅读一下上面讲述裸的单调队列的文字),然后统一将距离大于最大跳跃距离的节点删去(从队头开始删,直到删到距离小于最大跳跃距离的节点)。
    做完这两步后,就可以放心地做DP方程。

    如果还不懂就直接参考代码:

    bool Judge(int RP){
    	Max=M+RP;//能跳跃的最大距离 
    	Min=max(OO,M-RP);//能跳跃的最小距离 
    	for(register int i=1;i<=N;i++)
    		DP[i]=-INF;
    	//一定要注意,因为分数可能会是很小的负数 
    	DP[0]=0;//将第一格的值设为-1 
    	Front=1;Back=0;//初始化队列为空
    	// Front<=Back代表队列不为空 
    	register int j=0;
    	for(register int i=1;i<=N;i++){//枚举跳到的位置 
    		while(Num[i]-Num[j]>=Min&&j<i){//枚举从哪里开始跳 
    			if(DP[j]>-INF){//如果这个点可以作为起点 
    				while(Front<=Back&&DP[Queue[Back]]<=DP[j])
    					Back--;
    				//队列不为空,队尾节点没有现在枚举的节点优
    				//弹出队尾 
    				Queue[++Back]=j;//加入队尾 
    			}j++;//一直扫到小于跳跃距离 
    		}
    		while(Front<=Back&&Num[i]-Num[Queue[Front]]>Max)
    			Front++;//清空几个距离超过现有最大跳跃距离的节点 
    		if(Front<=Back)
    			DP[i]=max(DP[i],Mark[i]+DP[Queue[Front]]);//队列不为空,做方程 
    		if(DP[i]>=K) return true;//能达该分数 
    	}
    	return false;
    }
    

    总代码:

    #include "bits/stdc++.h"
    using namespace std;
    
    long long int Right,Left,Middle,Max,Min;
    long long int Queue[990000],Front,Back;
    long long int Num[990000],Mark[990000];
    const long long int INF=9999999999;
    //一定要注意,因为分数可能会是很小的负数 
    long long int N,M,K,ACanswer,OO=1;
    long long int DP[990000];
    
    bool Judge(int RP){
    	Max=M+RP;//能跳跃的最大距离 
    	Min=max(OO,M-RP);//能跳跃的最小距离 
    	for(register int i=1;i<=N;i++)
    		DP[i]=-INF;
    	//一定要注意,因为分数可能会是很小的负数 
    	DP[0]=0;//将第一格的值设为-1 
    	Front=1;Back=0;//初始化队列为空
    	// Front<=Back代表队列不为空 
    	register int j=0;
    	for(register int i=1;i<=N;i++){//枚举跳到的位置 
    		while(Num[i]-Num[j]>=Min&&j<i){//枚举从哪里开始跳 
    			if(DP[j]>-INF){//如果这个点可以作为起点 
    				while(Front<=Back&&DP[Queue[Back]]<=DP[j])
    					Back--;
    				//队列不为空,队尾节点没有现在枚举的节点优
    				//弹出队尾 
    				Queue[++Back]=j;//加入队尾 
    			}j++;//一直扫到小于跳跃距离 
    		}
    		while(Front<=Back&&Num[i]-Num[Queue[Front]]>Max)
    			Front++;//清空几个距离超过现有最大跳跃距离的节点 
    		if(Front<=Back)
    			DP[i]=max(DP[i],Mark[i]+DP[Queue[Front]]);//队列不为空,做方程 
    		if(DP[i]>=K) return true;//能达该分数 
    	}
    	return false;
    }
    
    int main(void){
    	scanf("%lld%lld%lld",&N,&M,&K);
    	for(register int i=1;i<=N;i++)
    		scanf("%lld%lld",&Num[i],&Mark[i]);
    	//读入数据,注意,用cin可能会爆 
    	ACanswer=-1;//不能达到要求就输出-1 
    	Right=Num[N];Left=0;
    	while(Left<=Right){//用二分法枚举花费的金币数 
    		Middle=(Right+Left)/2;
    		if(Judge(Middle)==true){//花费该金币可行,记录答案 
    			Right=Middle-1;//尝试更小的金币花费 
    			ACanswer=Middle;//记录 
    		}else Left=Middle+1;//不可行,增加金币数 
    	}
    	printf("%lld",ACanswer);//输出答案 
        return 0;
    }
    

    尾声

    单调队列的产生意义就是优化算法,今天的讲解只是它的冰山一角。
    祝愿各位读者大神在OI的道路上越走越远!

    若有疑问或意见,欢迎联系作者:
    洛谷ID:86624
    QQ:3303385057

    最后发一段寓意深刻的漫画:

    在这里插入图片描述

    谢谢!

    展开全文
  • 洛谷P1886 滑动窗口 【模板】单调队列 deque单调队列具体思路AC代码 虽然这个题提示了是单调队列的板子题,但是之前都没了解过单调队列这个数据结构,我还是下意识的暴力了一波,果不其然,TLE在最后一个样例上 暴力...

    洛谷P1886 滑动窗口 【模板】单调队列 deque


    虽然这个题提示了是单调队列的板子题,但是之前都没了解过单调队列这个数据结构,我还是下意识的暴力了一波,果不其然,TLE在最后一个样例上

    暴力解法复杂度:O(nk)
    单调队列解法复杂度: O(n) 差距还是很致命的

    单调队列

    百度百科给出的解释:单调队列,即单调递减或单调递增的队列。使用频率不高,但在有些程序中会有非同寻常的作用。

    为了维护这个单调性,在每次往队列中插入数据时,需要注意的就是,当前待插入到队尾的值是否破坏了当前队列的单调性,即如果是维护的一个单调递增的队列(队首元素始终维护最小值),那么当待插入的数比当前队尾的数小的时候,我们需要将队尾的元素弹出,直到满足:待插入的元素比队尾的元素大的时候再将其插入(这以操作就保证了整个队列的单调性,且不破坏原有数据的相对位置,单调递减的队列原理相同,条件相反)。

    由于传统的队列只能做到队尾进元素,队首出元素,但是要实现上述功能,就需要一种能够实现在队尾也能弹出元素的数据结构,因此我们引入双端队列(deque)。允许两端弹出,只允许一端插入的队列(允许两端插入,只允许一端弹出的也属于双端队列),刚好,在STL中前人已经为我们写好了这种数据结构,使用时需要引入deque这个头文件

    关于deque,详细的使用方法参见博客:点击进入

    具体思路

    为了严格的维护队列的单调性,我们采取将原序列数对应的下标放入队列中,维护原则按照前面所讲的方法,这样一来,我们就确保了队首的下标对应的数一定是某个区间的最小值(或最大值),但是这样维护的的值可能不是我们需要计算的对应值。

    对于本题中,由于我们需要计算的是在一个数组中[i-k+1,i ](1<=i<=n)区间的最小值和最大值,需要注意的是,当i小于输入的k的时候,即i到数组第一个元素小于要求的区间长度的时候,此时队列中的元素还不一定是最小(或最大)的值,我们继续将数组中的元素放入队列中,当i>=k的时候,就需要对在队首判断是否进行弹出操作,以输出最小值(或最大值),弹出的条件是当前队列中的x是否小于所求区间的左端点,小于则弹出,大于等于则输出该下表对应的数。

    AC代码

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <string>
    #include <math.h>
    #include <set>
    #include <map>
    #include <vector>
    #include <queue>
    #include <deque>
    #include <algorithm>
    using namespace std;
    const int maxn = 1e6 + 5;
    typedef long long ll;
    const int INF = 0x3f3f3f3f;
    int a[maxn];
    deque<int> q;
    int main()
    {
        int n,k;
        cin >> n >> k;
        for(int i = 1; i <= n; i++)
            cin >> a[i];
        for(int i = 1; i <= n; i++){ //计算最小值 
        	while(!q.empty() && a[q.back()] >= a[i])
        		q.pop_back();  //删除队尾较大的元素以维护单调性 
        	q.push_back(i);
        	if(i >= k){
        		while(!q.empty() && q.front() < i-k+1) //这里为什么是i-k+1? 
        			q.pop_front();					//我们把计算的区间理解成是一个左闭右闭的区间
        		cout << a[q.front()] << " "; 		// 例如 7 6 8 12 9 10 3   当i=6时  区间的开始应该是3 
    												//即当k = 4,i = 5的时候 对应的区间应该是 [5-4+1,5]
    												//当队列中的i不在这个区间中时,说明队头的下标对应的值不是当前这个区间的最小值 
        	}
        }
        cout << endl;
        while(!q.empty()) q.pop_back();
        for(int i = 1; i <= n; i++){ //计算最大值 
        	while(!q.empty() && a[q.back()] <= a[i])
        		q.pop_back();
        	q.push_back(i);
        	if(i >= k){
        		while(!q.empty() && q.front() < i-k+1)
        			q.pop_front();
        		cout << a[q.front()] << " "; 
        	}
        }
        cout << endl;
        return 0;
    }
    
    展开全文
  • 单调队列用法 deque

    2021-12-22 11:05:14
    deque 是 double-ended queue 的缩写,又称双端队列容器。 和 vector 不同的是,deque 还擅长在序列头部添加或删除元素,所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是,deque 容器中存储元素并不能保证...
  • # 特殊数据结构:单调队列前文讲了一种特殊的数据结构「单调栈」monotonic stack,解决了一类问题「Next Greater Number」,本文写一个类似的数据结构「单调队列」。也许这种数据结构的名字你没听过,其实没啥难的,...
  • 单调队列一般用于求区间内的最值问题 例题: P1886 滑动窗口 P2032 扫描 算法核心 维护一个单调递增或递减的双端队列 队头即是区间的最值 用一个结点存下标和值 struct node { int index; int value; }no; 为了...
  • 单调队列-原理详解(deque实现)

    万次阅读 多人点赞 2019-05-30 14:50:07
    一、单调队列的概念: 单调队列,即单调递减或单调递增的队列。 二、单调队列的性质: 1. 队列中的元素在原来的列表中的位置是由前往后的(随着循环顺序入队)。 2. 队列中元素的大小是单调递增或递减的。 三、...
  • C++中queue和deque的区别 queue只能从队尾插入,对头弹出 queue<int> q; q.push(0); // 插入 q.pop(); // 弹出 int tmp = q.front(); // 取对头元素 int tmp = q.back(); // 取队尾元素 deque 能从...
  • 1. 介绍单调栈/单调队列的应用场景; 2. 使用数组实现单调栈/单调队列,提高对数据结构的理解并提升效率
  • 滑动窗口在机试中是使用双端队列deque来进行,因为可以模拟滑动窗口的移动和加入新元素的操作,首先移动操作可以用t元素记录滑动窗口的头,然后滑动窗口需要移动的时候可以用q.pop_front(),t++的操作来模拟滑动窗口...
  • poj 2823 单调队列 deque写法

    千次阅读 2015-07-25 11:04:36
    #include <deque> using namespace std; typedef pair, int> P; #define maxn 1000000 + 10 deque<P> Q1; deque<P> Q2; int n, k; int Min[maxn], Max[maxn]; int main() { while(~scanf("%d%d", &n, &k)) { ...
  • 模板题:滑动窗口 STL(deque)实现: #include<cstdio> #include<...//双端队列 #define foo(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=1e6+7; int a[maxn]; ...
  • 涉及知识点:双端队列 deque 滑动窗口的最大值 由于需要直到某个区间的最大值,在区间向右滑动的时候,可以拆解为R向右一位,L也向右一位。 由于我们只需要最大值,所以deque里的内容单调递减的,开头的最大,记录...
  • 解法1:暴力法 ...解法2:单调队列 https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/mian-shi-ti-59-i-hua-dong-chuang-kou-de-zui-da-1-6/ 思想: ​ 用deque维护一.
  • 单调队列和单调栈

    2021-07-25 21:57:39
    维护单调队列性值的操作 入队操作:队尾入队,会把之前破坏单调性的元素都从队尾移出(维护单调性)。 出队操作:如果队首元素超出区间范围,就将元素从队首出队。 1.1 习题 1) 239. 滑动窗口最大值 一个整数数组
  • 求最大值同理,构造单调递减队列即可 【手写队列代码】 #include using namespace std; const int N = 1000010; int a[N], Q[N], hh, tt; int n, k; int main() { cin >> n >> k; for (int i = 0; i ; i++) cin >> a...
  • 我们可以维护一个左指针,保证进入单调队列里的值都满足前半部分的限制,后半部分的限制再由队首弹掉 收获: 单调队列每次弹出队列都只能满足一个条件 另一个条件我们用其他方式维护 感觉这个方法很常用【sTO ...
  • 提纲单调队列剑指 Offer 59 - II. 队列的最大值题目描述:请定义一个队列并实现函数 max_value 得到队列里的最大值若队列为空,pop_front 和 max_value 需要返回 -1示例 1:输入: ["MaxQueue","push_back","push_...
  • python刷题模板之单调队列
  • 多重背包问题的单调队列优化,适合对多重背包问题有一定了解的人阅读
  • 解法:该题可使用单调队列优化dpdpdp求解,首先,求出序列的前缀和,然后维护一个长度不大于mmm的双头队列,并且保持其是一个单调递增的队列,每次只需要以当前的前缀和与队头的前缀和相减就可以了,因为子序列和为...
  • 【C++】单调队列 详解

    千次阅读 2022-02-10 22:46:17
    目录单调队列1.1 单调队列介绍1.2 单调队列的应用1.2.1 滑动窗口最大值1.2.1.1 题目描述1.2.1.2 结题思路方法一(优先队列)方法二 (单调队列)1.3 单调队列的模拟实现1.4 其他例题 单调队列 1.1 单调队列介绍 单调...
  •   但是实际情况中,我们维持的单调栈与栈的数据结构式吻合的,而维持的单调队列则大部分可能都是双端队列,那么看到一个问题,我们如何确定到底使用来个结构来维持一个单调的序列的? 单调栈   我想有很多小伙伴...
  • 滑动窗口 /【模板】单调队列 题目描述 有一个长为 n n n 的序列 a a a,以及一个大小为 k k k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。 例如: The array is...
  • 双端队列deque容器: 关于deque最常用的有这几个函数: 都是成员函数 双端队列模板题:【洛谷】P2952 [USACO09OPEN]牛线Cow Line 1 #include<iostream> 2 #include<cstdio> 3 #include&...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,305
精华内容 2,522
关键字:

单调队列deque