洛谷 P1886 滑动窗口(单调队列)

时间:2021-08-23 21:49:41

题目链接

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.

洛谷 P1886 滑动窗口(单调队列)

输入输出格式

输入格式:

输入一共有两行,第一行为n,k。

第二行为n个数(<INT_MAX).

输出格式:

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

第二行为每次窗口滑动的最大值

输入输出样例

输入样例#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%的数据,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 滑动窗口(单调队列)的更多相关文章

  1. &lbrack;洛谷P1886&rsqb;滑动窗口 &lpar;单调队列&rpar;&lpar;线段树&rpar;

    ---恢复内容开始--- 这是很好的一道题 题目描述: 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口. 现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的 ...

  2. 洛谷P1886 滑动窗口(POJ&period;2823 Sliding Window)(区间最值)

    To 洛谷.1886 滑动窗口 To POJ.2823 Sliding Window 题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每 ...

  3. 洛谷 P1886 滑动窗口(单调队列)

    嗯... 题目链接:https://www.luogu.org/problem/P1886 首先这道题很典型,是标准的单调队列的模板题(也有人说单调队列只能解决这一个问题).这道题可以手写一个队列,也 ...

  4. 洛谷 P1886 滑动窗口

    题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...

  5. &lbrack;Luogu P1886&rsqb;滑动窗口--单调队列入门

    题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...

  6. 洛谷 P1886 滑动窗口 &lpar;数据与其他网站不同。。&rpar;

    题目描述 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. 例如: The array i ...

  7. 洛谷——P1886 滑动窗口&vert;&vert; POJ——T2823 Sliding Window

    https://www.luogu.org/problem/show?pid=1886#sub || http://poj.org/problem?id=2823 题目描述 现在有一堆数字共N个数字( ...

  8. 洛谷P1886--滑动窗口&lpar;单调队列模板&rpar;

    https://www.luogu.org/problemnew/show/P1886 单调队列的操作上比普通队列多了可以从尾端出队 单调队列保持队内元素单调递增/递减,以保证队首元素为最小/最大元素 ...

  9. &lbrack;POJ2823&rsqb;&lbrack;洛谷P1886&rsqb;滑动窗口 Sliding Window

    题目大意:有一列数,和一个窗口,一次能框连续的s个数,初始时窗口在左端,不断往右移动,移到最右端为止,求每次被框住的s个数中的最小数和最大数. 解题思路:这道题是一道区间查询问题,可以用线段树做.每个 ...

随机推荐

  1. 微信JSSDK javascript 开发 代码片段,仅供参考

    最全面最专业的微信公众平台开发教程:http://www.cnblogs.com/txw1958/p/weixin-js-sdk-demo.html 比较完整的分享教程:http://www.cnbl ...

  2. Sublime Text 2&sol;3安装使用及常用插件

    一.介绍 Sublime Text 是一款较新的编辑器,它轻量.简洁.高效,良好的扩展性以及跨平台等特性,使得越来越多的开发人员喜爱.它是一款收费的商业软件,但可以免费无限制无限期的试用,只会偶尔提醒 ...

  3. centos6&period;5 安装cmake 3&period;3&period;2

    os:centos6.5 cmake版本:3.3.2 安装编译源码所需的工具和库 yum install gcc gcc-c++ ncurses-devel perl 下载cmake 使用wget工具 ...

  4. 为网站添加网址图标favicon&period;ico

    今天终于有时间把domety的图标设计好,并显示在了网站地址前面.如果你还不知道怎么把自己的图标放到网站上,今天DDBug就和你分享一下实现方法. 制作图标 首先是准备一张ico图标,你可以从网上搜索 ...

  5. D&amp&semi;F学数据结构系列——二叉堆

    二叉堆(binary heap) 二叉堆数据结构是一种数组对象,它可以被视为一棵完全二叉树.同二叉查找树一样,堆也有两个性质,即结构性和堆序性.对于数组中任意位置i上的元素,其左儿子在位置2i上,右儿 ...

  6. 在Windows Server 2008上部署SVN代码管理总结

    这段时间在公司开发Flex程序,所以使用TortoiseSVN作为团队代码管理器,今天在公司服务器上部署SVN服务器,并实验成功,总结如下: 服务器环境: 操作系统:Windows Server 20 ...

  7. 所有Mac用户都需要知道的9个实用终端命令行&lt&semi;转&gt&semi;

    转自 http://www.macx.cn/thread-2075903-1-1.html 通常情况下,只有高端用户才会经常用到终端应用.这并不意味着命令行非常难学,有的时候命令行可以轻松.快速的解决 ...

  8. C&plus;&plus; 数据结构学习二&lpar;单链表&rpar;

    模板类 //LinkList.h 单链表#ifndef LINK_LIST_HXX#define LINK_LIST_HXX#include <iostream>using namespa ...

  9. Spring data redis的一个bug

    起因 前两天上线了一个新功能,导致线上业务的缓存总是无法更新,报错也是非常奇怪,redis.clients.jedis.exceptions.JedisConnectionException: Unk ...

  10. 获取DOM节点的几种方式

    DOM 是一个树形结构,操作一个DOM节点,实际上就是这几个操作:更新.删除.添加.遍历 在操作DOM节点之前,需要通过各种方式先拿到这个DOM节点,常用的方法有: 一.通过元素类型的方法来操作: d ...