中国移动 分布式 微信商家收款 ssh命令 string inheritance mysqli datepicker onclick Vanilla JS underscorejs alertifyjs 后台系统模板 网络游戏server编程 windows安装python环境 java时间戳转换成时间 java对象和类 java平台 python源码下载 pascal教程 微信python退出程序 workflow中文 python的用途 html特殊符号 big5 skycc组合营销软件 亚索刀光 medcalc js切割字符串 wegame更新失败 什么是人肉搜索 quickchm qq流览器下载 omg小北 上单艾克出装 语音转文字转换器 python简单代码 ibeacon定位 python游戏编程 答题器下载
当前位置: 首页 > 学习教程  > 编程语言

单调队列(洛谷p1886)模板题

2021/2/13 20:13:31 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

例题:洛谷p1886滑动窗口 有一个长为 n的序列 a,以及一个大小为 k的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。 例如: The array is [1,3,-1,-3,5,3,6,7]&#xff…

例题:洛谷p1886滑动窗口

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

例如:

The array is [1,3,-1,-3,5,3,6,7], and k = 3。
在这里插入图片描述

单调队列有两个性质

1.队列中的元素其对应在原来的列表中的顺序必须是单调递增的。

2.队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)

单调队列与普通队列不一样的地方就在于单调队列既可以从队首出队,也可以从队尾出队。

分析

以最小值为例:构造一个单调队列q[i],记h为元素下标,q中存下标。第一次:q={1};第二次:q={1,2}(因为3>1且在范围内);第三次:q={3}(因为队列单调递增,-1最小,所以挤掉1和3,找最小值的时候也不会轮到它们);第四次:q={4}(1已经在外面了。-3<-1果断挤掉);第五次:q={4,5}(5>-3 可以作为候选人);第六次:q={4,6}(果断挤掉,有比5合适的候选人);第七次:b={6,7}(4不在范围内,出列);第八次:b={6,7,8}

每次都输出队列中的第一个元素**(因为每次只有满足待入队的元素比队列中队尾元素更大才可以入队,否则需要将比它小的所有队列中的元素全部出队,再将它入队,因此队列始终单调递增,不可能存在比第一个元素更小的元素)**。

以此维护队列中元素序号的单调性,得到结果。

只是比较判断,时间复杂度很小。

相等的值也要挤掉。

最大值同理。
上代码:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath> 
using namespace std;
int n,k;
int q1[1000001],q2[1000001];
int a[1000001];
int min_deque()//求窗口内最小值 
{
	int l=1,r=0;//初始化队列左右下标(l为左,为右),只有这样初始化,l<=r才可以保证队列不为空。) 
	for(int i=1;i<=n;i++)
	{
		while(l<=r&&q1[l]+k<=i) l++;// q1[l]+k<=i表明队首元素已经不在窗口内,应将队首出列 
		while(l<=r&&a[i]<a[q1[r]]) r--;//若待入队元素比 队尾元素小,队尾出队,直到队内没有比它再大的元素为止,保证队列的单调递增 
		q1[++r]=i;//入队 
		if(i>=k) printf("%d ",a[q1[l]]);//当i<k时,说明窗口大小没有达到k,不会有输出,当i>=k后,每次窗口滑动都应输出队首 
	}
	cout<<endl;//不要忘记换行 
}
int max_deque()//求窗口内的最大值,步骤类似最小值 
{
	int l=1,r=0;
	for(int i=1;i<=n;i++)
	{
		while(l<=r&&q2[l]+k<=i) l++;
		while(l<=r&&a[i]>a[q2[r]]) r--;
		q2[++r]=i;
		if(i>=k) printf("%d ",a[q2[l]]);
	}
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	min_deque();
	max_deque();
	return 0;
}//自认为码风还是比较简洁的(#^.^#) 

本文链接: http://www.dtmao.cc/news_show_700414.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?