当前位置: 首页 > news >正文

P1886 滑动窗口 /【模板】(双端队列)+双端队列用法

例题

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

例如:

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

输入格式

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

输出格式

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

输入输出样例

输入 

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

输出 

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

说明/提示

【数据范围】
对于 50%50% 的数据,1≤n≤105;
对于 100%100% 的数据,1≤k≤n≤106,ai​∈[−2^31,2^31)。

代码实现

#include<iostream>
#include<queue>
using namespace std;
const int N=1e6+10;
int a[N],b[N],ans1[N],ans2[N];int main(){int n,m,c=0;cin>>n>>m;deque<int>s1,s2;for(int i=1;i<=n;i++){scanf("%d",&a[i]);b[i]=a[i];while(s1.size()&&a[s1.back()]>a[i])s1.pop_back();while(s2.size()&&b[s2.back()]<b[i])s2.pop_back();s1.push_back(i);s2.push_back(i);while(s1.front()<=i-m)s1.pop_front();while(s2.front()<=i-m)s2.pop_front();if(i>=m){ans1[++c]=a[s1.front()];ans2[c]=b[s2.front()];}}for(int i=1;i<=c;i++)cout<<ans1[i]<<" ";cout<<endl;for(int i=1;i<=c;i++)cout<<ans2[i]<<" ";cout<<endl;return 0;
} 

滑动窗口模板

//求窗口内的最小值
deque<int>q;
for(int i=1;i<=n;i++){scanf("%d",&a[i]);//如果新元素小于尾部元素,就把尾部元素删除 while(q.size()&&a[q.back()]>a[i])q.pop_back();//把新元素的下标加入队列尾部q.push_back(i); //如果第一个元素的下标超出窗口范围,就把第一个元素删除 while(q.front()<=i-m)q.pop_front(); if(i>=m)printf("%d\n",a[q.front()]); } 

双端队列常用操作

deque 容器的成员函数
函数成员函数功能
begin()返回指向容器中第一个元素的迭代器。
end()返回指向容器最后一个元素所在位置后一个位置的迭代器,通常和 begin() 结合使用。
rbegin()返回指向最后一个元素的迭代器。
rend()返回指向第一个元素所在位置前一个位置的迭代器。
cbegin()和 begin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
cend()和 end() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crbegin()和 rbegin() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
crend()和 rend() 功能相同,只不过在其基础上,增加了 const 属性,不能用于修改元素。
size()返回实际元素个数。
max_size()返回容器所能容纳元素个数的最大值。这通常是一个很大的值,一般是 232-1,我们很少会用到这个函数。
resize()改变实际元素的个数。
empty()判断容器中是否有元素,若无元素,则返回 true;反之,返回 false。
shrink _to_fit()将内存减少到等于当前元素实际所使用的大小。
at()使用经过边界检查的索引访问元素。
front()返回第一个元素的引用。
back()返回最后一个元素的引用。
assign()用新元素替换原有内容。
push_back()在序列的尾部添加一个元素。
push_front()在序列的头部添加一个元素。
pop_back()移除容器尾部的元素。
pop_front()移除容器头部的元素。
insert()在指定的位置插入一个或多个元素。
erase()移除一个元素或一段元素。
clear()移出所有的元素,容器大小变为 0。
swap()交换两个容器的所有元素。
emplace()在指定的位置直接生成一个元素。
emplace_front()在容器头部生成一个元素。和 push_front() 的区别是,该函数直接在容器头部构造元素,省去了复制移动元素的过程。
emplace_back()在容器尾部生成一个元素。和 push_back() 的区别是,该函数直接在容器尾部构造元素,省去了复制移动元素的过程。
http://www.lryc.cn/news/151847.html

相关文章:

  • 网络渗透day6-面试01
  • Docker 及 Docker Compose 安装指南
  • Gitlab创建一个空项目
  • C语言-内存分布(STM32内存分析)
  • Linux上配置NAT
  • springboot实现简单的消息对话
  • 「Tech初见」Linux驱动之blkdev
  • ssh配置(二、登录服务器)
  • pytorch异常——RuntimeError:Given groups=1, weight of size..., expected of...
  • 【FPGA项目】沙盘演练——基础版报文收发
  • 【C++技能树】继承概念与解析
  • 计算机网络 第二节
  • 无涯教程-机器学习 - 矩阵图函数
  • Redis 高可用与集群
  • 修改文件名后Git仓上面并没有修改
  • Linux 信号
  • 深入探讨梯度下降:优化机器学习的关键步骤(二)
  • 高频算法面试题
  • Hive-启动与操作(2)
  • css transition 指南
  • LeetCode 面试题 02.05. 链表求和
  • 一米脸书营销软件
  • vue 根据数值判断颜色
  • Hugging Face 实战系列 总目录
  • 国标视频云服务EasyGBS国标视频平台迁移服务器后无法启动的问题解决方法
  • HTML <th> 标签
  • HTTP/1.1协议中的响应报文
  • TDengine函数大全-选择函数
  • 非关系型数据库Redis的安装
  • oracle 创建数据库