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()]); }
双端队列常用操作
| 函数成员 | 函数功能 |
|---|---|
| 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() 的区别是,该函数直接在容器尾部构造元素,省去了复制移动元素的过程。 |
相关文章:
P1886 滑动窗口 /【模板】(双端队列)+双端队列用法
例题 有一个长为 n 的序列 a,以及一个大小为 k 的窗口。现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值。 例如: The array is [1,3,−1,−3,5,3,6,7],and k3。 输入格式 输入一共有两行…...
网络渗透day6-面试01
😉 和渗透测试相关的面试问题。 介绍 如果您想自学网络渗透,有许多在线平台和资源可以帮助您获得相关的知识和技能。以下是一些受欢迎的自学网络渗透的平台和资源: Hack The Box: Hack The Box(HTB)是一个受欢迎的平…...
Docker 及 Docker Compose 安装指南
Docker 是一个开源的容器化平台,可以帮助我们快速构建、打包和运行应用程序。而 Docker Compose 则是用于管理多个容器应用的工具,可以轻松定义和管理多个容器之间的关系。现在,让我们开始安装过程吧! docker 安装 apt安装 sudo…...
Gitlab创建一个空项目
1. 创建项目 Project slug是访问地址的后缀,跟前边的ProjectUrl拼在一起,就是此项目的首页地址; Visibility Level选择默认私有即可,选择内部或者公开,就会暴露代码。 勾选Readme选项,这样项目内默认会带…...
C语言-内存分布(STM32内存分析)
C/C内存分布 一、内存组成二、静态区域文本段 (Text / 只读区域 RO)已初始化读写数据段(RW data -- Initialized Data Segment)未初始化数据段(BSS -- Block Started by Symbol) 三、动态区域堆(…...
Linux上配置NAT
Linux系统上实现NAT上网是一个挑战性的任务,需要对操作系统进行合理的配置。本文将概述在Linux上实现NAT上网,并给出相应的工作步骤。 NAT,即Network Address Translation,是一种网络部署技术,可以在peivate network&…...
springboot实现简单的消息对话
目录 一、前言 二、实战步骤 步骤 1: 步骤 2: 步骤 3: 步骤 4: 一、前言 要在Spring Boot项目中实现消息对话,你可以使用WebSocket技术。WebSocket是一种在客户端和服务器之间提供实时双向通信的协议。 二、实…...
「Tech初见」Linux驱动之blkdev
目录 一、Motivation二、SolutionS1 - 块设备驱动框架(1)注册块设备(2)注销块设备(3)申请 gendisk(4)删除 gendisk(5)将 gendisk 加入 kernel(6&a…...
ssh配置(二、登录服务器)
一. 登录 linux 服务器的两种方式 使用 ssh用户名密码 的方式登录,但这种方式不安全,密码太简单容易被暴力破解,密码太复杂又不容易记。使用 ssh公私钥 的方式登录。 以上两种方式都可以在图形化软件工具中配置,例如 finalshell…...
pytorch异常——RuntimeError:Given groups=1, weight of size..., expected of...
文章目录 省流异常报错异常截图异常代码原因解释修正代码执行结果 省流 nn.Conv2d 需要的输入张量格式为 (batch_size, channels, height, width),但您的示例输入张量 x 是 (batch_size, height, width, channels)。因此,需要对输入张量进行转置。 注意…...
【FPGA项目】沙盘演练——基础版报文收发
第1个虚拟项目 前言 点灯开启了我们的FPGA之路,那么我们来继续沙盘演练。 用一个虚拟项目,来入门练习,以此步入数字逻辑的…...
【C++技能树】继承概念与解析
Halo,这里是Ppeua。平时主要更新C,数据结构算法,Linux与ROS…感兴趣就关注我bua! 继承 0. 继承概念0.1 继承访问限定符 1. 基类和派生类对象赋值兼容转换2. 继承中的作用域3. 派生类中的默认成员函数4.友元5.继承中的静态成员6.菱…...
计算机网络 第二节
目录 一,计算机网络的分类 1.按照覆盖范围分 2.按照所属用途分 二,计算机网络逻辑组成部分 1.核心部分 (通信子网) 1.1电路交换 1.2 分组交换 两种方式的特点 重点 2.边缘部分 (资源子网) 进程通信的方…...
无涯教程-机器学习 - 矩阵图函数
相关性是有关两个变量之间变化的指示,在前面的章节中,无涯教程讨论了Pearson的相关系数以及相关的重要性,可以绘制相关矩阵以显示哪个变量相对于另一个变量具有较高或较低的相关性。 在以下示例中,Python脚本将为Pima印度糖尿病数…...
Redis 高可用与集群
Redis 高可用与集群 虽然 Redis 可以实现单机的数据持久化,但无论是 RDB 也好或者 AOF 也好,都解决 不了单点宕机问题,即一旦单台 redis 服务器本身出现系统故障、硬件故障等问题后, 就会直接造成数据的丢失,因此需要…...
修改文件名后Git仓上面并没有修改
场景: 我在本地将文件夹名称由Group → group ,执行git push 后,远程分支上的文件名称并没有修改。 原因: 是我绕过了git 直接使用了系统的重命名操作。 在 Git 中,对于已经存在的文件或文件夹进行大小写重命名是一个敏感的操作…...
Linux 信号
目录 基本概念信号的分类可靠信号与不可靠信号实时信号与非实时信号 常见信号与默认行为进程对信号的处理signal()函数sigaction()函数 向进程发送信号kill()函数raise() alarm()和pause()函数alarm()函数pause()函数 信号集初始化信号集测试信号是否在信号集中 获取信号的描述…...
深入探讨梯度下降:优化机器学习的关键步骤(二)
文章目录 🍀引言🍀eta参数的调节🍀sklearn中的梯度下降 🍀引言 承接上篇,这篇主要有两个重点,一个是eta参数的调解;一个是在sklearn中实现梯度下降 在梯度下降算法中,学习率…...
高频算法面试题
合并两个有序数组 const merge (nums1, nums2) > {let p1 0;let p2 0;const result [];let cur;while (p1 < nums1.length || p2 < nums2.length) {if (p1 nums1.length) {cur nums2[p2];} else if (p2 nums2.length) {cur nums1[p1];} else if (nums1[p1] &…...
Hive-启动与操作(2)
🥇🥇【大数据学习记录篇】-持续更新中~🥇🥇 个人主页:beixi 本文章收录于专栏(点击传送):【大数据学习】 💓💓持续更新中,感谢各位前辈朋友们支持…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
wpf在image控件上快速显示内存图像
wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像(比如分辨率3000*3000的图像)的办法,尤其是想把内存中的裸数据(只有图像的数据,不包…...
基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)
引言 在嵌入式系统中,用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例,介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单,执行相应操作,并提供平滑的滚动动画效果。 本文设计了一个…...
命令行关闭Windows防火墙
命令行关闭Windows防火墙 引言一、防火墙:被低估的"智能安检员"二、优先尝试!90%问题无需关闭防火墙方案1:程序白名单(解决软件误拦截)方案2:开放特定端口(解决网游/开发端口不通)三、命令行极速关闭方案方法一:PowerShell(推荐Win10/11)方法二:CMD命令…...
