题目链接
https://www.luogu.org/problemnew/show/P1886
题目描述
现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。
例如:
The array is [1 3 -1 -3 5 3 6 7], and k = 3.
输入输出格式
输入格式:
输入一共有两行,第一行为n,k。
第二行为n个数(<INT_MAX).
输出格式:
输出共两行,第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
8 3
1 3 -1 -3 5 3 6 7
-1 -3 -3 -3 3 3
3 3 5 5 6 7
说明
50%的数据,n<=10^5
100%的数据,n<=10^6
解题思路
先理解文意:对于给定一个长度为n的序列,找出所有长为k的区间的最大值(最小值)。
首先很多人会想到,枚举每一个长为k的区间,然后遍历一遍,找到最大值(最小值),这样的时间复杂度是o(nk)的,显然超时。
所以我们需要换一种思路。
单调队列:单调队列就是一个一直保持单调性(递增或递减)的长度最大为k的双端队列。
我们维护这样一个单调队列,使它队首元素即为要求的最大值(最小值)。
所以本题的核心是:怎样维护一个单调队列。
在此举例求最大值:对于任意读入的元素,我们不放设为in,首先判断队列是否为空,如果队列为空,就一定要加入队列。若不为空,就一直比较队列末尾的元素,不放设为f,如果f<in,就把f弹出去,砍掉。为什么呢?因为f能做到的,in一定也能做到,in>f,所以在一定范围内,答案有可能是in,但永远不可能是f。(这里有一个有趣的类比,如果一位OIer比你年轻还比你强,那你就没法超越他了。——Kevin大佬)。还有一个问题,就是滑动窗口长度最大是k,所以我们需要用结构体保存每一个数的编号和数值,如果in的编号和队首的编号的差>=k,就把队首砍掉,这是显然的。
这样,由于每一个元素只进入队列一次,所以时间复杂度就变成o(n)了。
话不多说,看代码。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<ctime> //还是写了一大堆没用的头文件
using namespace std;
int n,k;
int maxx[],minn[]; //由于输出要求,需要先用数组存好答案
struct num{ //结构体储存编号和数值
int cnt,value;
num(int a,int b):cnt(a),value(b){} //结构体构造函数,作用是在定义结构体的时候,就会给cnt和value赋值。用法具体看29行或者39行代码
};
deque<num> q1,q2; //定义两个双端队列,q1储存最大值,q2储存最小值
void makeq1(int i,int in){ //makeq1处理最大值
if(q1.empty()) q1.push_back(num(i,in));//队列为空时直接入队
else{
num f=q1.front();
if(i>f.cnt+k-) q1.pop_front();//判断队列长度是否超过k
if(!q1.empty()){ //队尾弹不断弹出操作
num b=q1.back();
while(b.value<in){
q1.pop_back();
if(q1.empty()) break;
b=q1.back();
}
}
q1.push_back(num(i, in));
}
}
void makeq2(int i,int in){ //makeq2处理最小值
if(q2.empty()) q2.push_back(num(i,in));//队列为空时直接入队
else{
num f=q2.front();
if(i>f.cnt+k-) q2.pop_front(); //判断队列长度是否超过k
if(!q2.empty()){ //队尾弹不断弹出操作
num b=q2.back();
while(b.value>in){ //和makeq1不同的地方
q2.pop_back();
if(q2.empty()) break;
b=q2.back();
}
}
q2.push_back(num(i, in));
}
}
int main()
{
cin>>n>>k;
for(int i=;i<=n;i++){
int in;
cin>>in;
makeq1(i,in);
makeq2(i,in);
if(i>=k){ //如果长度达到k,就储存结果
maxx[i]=q1.front().value;
minn[i]=q2.front().value;
}
}
for(int i=k;i<=n;i++) cout<<minn[i]<<" "; //注意输出格式
cout<<endl;
for(int i=k;i<=n;i++) cout<<maxx[i]<<" ";
return ;
}
AC代码
洛谷 P1886 滑动窗口(单调队列)的更多相关文章
-
[洛谷P1886]滑动窗口 (单调队列)(线段树)
---恢复内容开始--- 这是很好的一道题 题目描述: 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口. 现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的 ...
-
洛谷P1886 滑动窗口(POJ.2823 Sliding Window)(区间最值)
To 洛谷.1886 滑动窗口 To POJ.2823 Sliding Window 题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每 ...
-
洛谷 P1886 滑动窗口(单调队列)
嗯... 题目链接:https://www.luogu.org/problem/P1886 首先这道题很典型,是标准的单调队列的模板题(也有人说单调队列只能解决这一个问题).这道题可以手写一个队列,也 ...
-
洛谷 P1886 滑动窗口
题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...
-
[Luogu P1886]滑动窗口--单调队列入门
题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...
-
洛谷 P1886 滑动窗口 (数据与其他网站不同。。)
题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...
-
洛谷——P1886 滑动窗口|| POJ——T2823 Sliding Window
https://www.luogu.org/problem/show?pid=1886#sub || http://poj.org/problem?id=2823 题目描述 现在有一堆数字共N个数字( ...
-
洛谷P1886--滑动窗口(单调队列模板)
https://www.luogu.org/problemnew/show/P1886 单调队列的操作上比普通队列多了可以从尾端出队 单调队列保持队内元素单调递增/递减,以保证队首元素为最小/最大元素 ...
-
[POJ2823][洛谷P1886]滑动窗口 Sliding Window
题目大意:有一列数,和一个窗口,一次能框连续的s个数,初始时窗口在左端,不断往右移动,移到最右端为止,求每次被框住的s个数中的最小数和最大数. 解题思路:这道题是一道区间查询问题,可以用线段树做.每个 ...
随机推荐
-
微信JSSDK javascript 开发 代码片段,仅供参考
最全面最专业的微信公众平台开发教程:http://www.cnblogs.com/txw1958/p/weixin-js-sdk-demo.html 比较完整的分享教程:http://www.cnbl ...
-
Sublime Text 2/3安装使用及常用插件
一.介绍 Sublime Text 是一款较新的编辑器,它轻量.简洁.高效,良好的扩展性以及跨平台等特性,使得越来越多的开发人员喜爱.它是一款收费的商业软件,但可以免费无限制无限期的试用,只会偶尔提醒 ...
-
centos6.5 安装cmake 3.3.2
os:centos6.5 cmake版本:3.3.2 安装编译源码所需的工具和库 yum install gcc gcc-c++ ncurses-devel perl 下载cmake 使用wget工具 ...
-
为网站添加网址图标favicon.ico
今天终于有时间把domety的图标设计好,并显示在了网站地址前面.如果你还不知道怎么把自己的图标放到网站上,今天DDBug就和你分享一下实现方法. 制作图标 首先是准备一张ico图标,你可以从网上搜索 ...
-
D&;F学数据结构系列——二叉堆
二叉堆(binary heap) 二叉堆数据结构是一种数组对象,它可以被视为一棵完全二叉树.同二叉查找树一样,堆也有两个性质,即结构性和堆序性.对于数组中任意位置i上的元素,其左儿子在位置2i上,右儿 ...
-
在Windows Server 2008上部署SVN代码管理总结
这段时间在公司开发Flex程序,所以使用TortoiseSVN作为团队代码管理器,今天在公司服务器上部署SVN服务器,并实验成功,总结如下: 服务器环境: 操作系统:Windows Server 20 ...
-
所有Mac用户都需要知道的9个实用终端命令行<;转>;
转自 http://www.macx.cn/thread-2075903-1-1.html 通常情况下,只有高端用户才会经常用到终端应用.这并不意味着命令行非常难学,有的时候命令行可以轻松.快速的解决 ...
-
C++ 数据结构学习二(单链表)
模板类 //LinkList.h 单链表#ifndef LINK_LIST_HXX#define LINK_LIST_HXX#include <iostream>using namespa ...
-
Spring data redis的一个bug
起因 前两天上线了一个新功能,导致线上业务的缓存总是无法更新,报错也是非常奇怪,redis.clients.jedis.exceptions.JedisConnectionException: Unk ...
-
获取DOM节点的几种方式
DOM 是一个树形结构,操作一个DOM节点,实际上就是这几个操作:更新.删除.添加.遍历 在操作DOM节点之前,需要通过各种方式先拿到这个DOM节点,常用的方法有: 一.通过元素类型的方法来操作: d ...