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

C - 滑动窗口 /【模板】单调队列

Description

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

例如:

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

Input

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

Output

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

Sample 1

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

Hint

【数据范围】
对于50% 的数据,1≤n≤10^5;
对于100% 的数据,1≤k≤n≤10^6,ai​∈[−231,231)。

 

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], maxq[N], minq[N];
int n, m;//h是队头,用于输出答案;t是队尾,用于加入和删除元素
//注意:对头为左,队尾为右,队头只出,队尾可出可进;因此若队内有元素,则h<=t
//max队内的元素因保持单调递减的性质,加入的不是元素值,而是元素所在数组a中的下标
void maxfind() {int h = 0, t = -1;for (int i = 1; i <= n; i++){if (h <= t && maxq[h] <= i - m) h++;    //不在当前滑动窗口的元素删除while (h <= t && a[i] >= a[maxq[t]]) t--; //a[i]为当前元素,若当前元素大于队尾的元素,则需要删除,时其满足单调递减的性质maxq[++t] = i;   //加入新元素的下标if(i>=m) cout << a[maxq[h]] << " ";//输出结果}
}
//原理同上
void minfind() {int h = 0, t = -1;for (int i = 1; i <= n; i++){if (h <= t && minq[h] <= i - m) h++;while (h <= t && a[i] <= a[minq[t]]) t--;minq[++t] = i;if(i>=m) cout << a[minq[h]] << " ";}
}int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];minfind();cout << endl;maxfind();return 0;
}

 单调队列模板(滑动窗口)_滑动窗口 /【模板】单调队列_胡牧之.的博客-CSDN博客

相关文章:

C - 滑动窗口 /【模板】单调队列

Description 有一个长为 n 的序列 a&#xff0c;以及一个大小为 k 的窗口。现在这个从左边开始向右滑动&#xff0c;每次滑动一个单位&#xff0c;求出每次滑动后窗口中的最大值和最小值。 例如&#xff1a; The array is [1,3,−1,−3,5,3,6,7] and k3。 Input 输入一共有…...

工厂人员作业行为动作识别检测算法

工厂人员作业行为动作识别检测算法通过yolov7python深度学习算法框架模型&#xff0c;工厂人员作业行为动作识别检测算法实时识别并分析现场人员操作动作行为是否符合SOP安全规范流程作业标准&#xff0c;如果不符合则立即抓拍告警提醒。Python是一种由Guido van Rossum开发的通…...

【数据结构】顺序表详解

当我们写完通讯录后&#xff0c;顺序表肯定难不倒你&#xff0c;跟着小张一起来学习顺序表吧&#xff01; 线性表 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构&#xff0c;常见的线性表&#x…...

HTML 播放器效果

效果图 实现代码 <!DOCTYPE HTML> <html><head><title>爱看动漫社区 | 首页 </title><link href"css/bootstrap.css" relstylesheet typetext/css /><!-- jQuery --><script src"js/jquery-1.11.0.min.js"…...

C++常用23种设计模式总结(三)------装饰模式

往期回顾 C常用23种设计模式总结(一)------单例模式 C常用23种设计模式总结(二)------观察者模式 什么是装饰模式 装饰模式是一种结构型设计模式&#xff0c;它允许你在运行时为对象动态添加新的行为。该模式通过将对象放入包装器中来实现这一点&#xff0c;这个包装器会实现与…...

选择O型圈时要考虑哪些因素?

为您的应用选择正确的O型圈对于确保适当的密封和较佳性能至关重要。O型圈可用的材料和尺寸多种多样&#xff0c;做出正确的选择可能需要知道一些重要的知识点。在本文中&#xff0c;我们将讨论选择O型圈时需要考虑的一些关键因素。 1、材料兼容性&#xff1a;先要考虑的因素是…...

安全管理中心技术测评要求项

1.系统管理-通过系统管理员进行系统管理操作 1-0/2-2/3-2/4-2 a&#xff09;对系统管理员进行身份鉴别&#xff0c;只允许其通过特定的命令或操作界面进行系统管理操作&#xff0c;并对这些操作进行审计 b&#xff09;通过系统管理员对系统的资源和运行进行配置、控制和管理&am…...

Hibernate(Spring Data)抓取策略

文章目录 示例代码放到最后&#xff0c;使用的是Springboot 项目1. 简介2. Hibernate抓取策略分类2.1 即时加载&#xff08;Eager Loading&#xff09;2.2 延迟加载&#xff08;Lazy Loading&#xff09;2.3 子查询加载&#xff08;Subselect Loading&#xff09;2.4 基于批处理…...

【高阶数据结构】map和set的介绍和使用 {关联式容器;键值对;map和set;multimap和multiset;OJ练习}

map和set的介绍和使用 一、关联式容器 关联式容器和序列式容器是C STL中的两种不同类型的容器。 关联式容器是基于键值对的容器&#xff0c;其中每个元素都有一个唯一的键值&#xff0c;可以通过键值来访问元素。关联式容器包括set、multiset、map和multimap。 序列式容器是…...

系统架构技能之设计模式-单件模式

一、开篇 其实我本来不是打算把系统架构中的一些设计模式单独抽出来讲解的&#xff0c;因为很多的好朋友也比较关注这方面的内容&#xff0c;所以我想通过我理解及平时项目中应用到的一 些常见的设计模式,拿出来给大家做个简单讲解&#xff0c;我这里只是抛砖引玉&#xff0c…...

Redis进阶 - JVM进程缓存

原文首更地址&#xff0c;阅读效果更佳&#xff01; Redis进阶 - JVM进程缓存 | CoderMast编程桅杆https://www.codermast.com/database/redis/redis-advance-jvm-process-cache.html 传统缓存的问题 传统的缓存策略一般是请求到达 Tomcat 后&#xff0c;先查询 Redis &…...

SD-WAN带您告别高成本、单一功能和安全性差

现今&#xff0c;随着企业规模不断扩大和分散办公越来越普遍&#xff0c;企业对于网络的需求也变得越来越高。然而&#xff0c;传统的组网方式面临着很多的问题&#xff0c;比如&#xff1a;成本高、功能单一、安全性差等问题。 传统组网方式有哪些&#xff1f; 传统的组网方式…...

面试必备:揭秘ArrayList和LinkedList,区别、优缺点与使用场景

大家好&#xff0c;我是你们的小米&#xff01;今天我要跟大家聊一个在面试中经常被问到的热门话题——ArrayList和LinkedList的区别、优缺点以及它们的使用场景。作为程序员&#xff0c;掌握这些知识点不仅可以在面试中脱颖而出&#xff0c;还能帮助我们更好地在项目中选择合适…...

【局部活动轮廓】使用水平集方法实现局部活动轮廓方法研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

Git 同步远程新的同名分支

背景 因为远程分支的提交记录过多&#xff0c;导致本地的commit内容过大&#xff0c;会产生一些问题&#xff1a; 第一次拉取时间较长占用本地和远程的存储 原因 因为项目已有一些年头&#xff0c;若是每次文件提交比较大&#xff0c;那么占用空间就更大 解决方案 该方案…...

PingCode DevOps 团队:企业CICD流水线可能会遇到的问题及解法

CICD 流水线是指一系列自动化的构建、测试和部署步骤&#xff0c;用于将应用程序从开发到生产环境的过程。在 CICD 流水线中&#xff0c;每个步骤都是自动化的&#xff0c;并且在完成后会触发下一个步骤的执行。 CICD 的价值 CICD 流水线可以帮助团队更快地交付产品&#xff…...

【LeetCode题目详解】第九章 动态规划part01 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯 (day38补)

本文章代码以c为例&#xff01; 一、力扣第509题&#xff1a;斐波那契数 题目&#xff1a; 斐波那契数 &#xff08;通常用 F(n) 表示&#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始&#xff0c;后面的每一项数字都是前面两项数字的和。也就是&#xff1a…...

图像处理 信号处理板 设计原理图:367-基于zynq XC7Z100 FMC接口通用计算平台

基于zynq XC7Z100 FMC接口通用计算平台 一、板卡概述 板卡由SoC XC7Z100-2FFG900I芯片来完成卡主控及数字信号处理&#xff0c;XC7Z100内部集成了两个ARM Cortex-A9核和一个kintex 7的FPGA&#xff0c;通过PL端FPGA扩展FMC、光纤、IO等接口&#xff0c;PS端ARM扩展网络、USB、R…...

PHP中header()的七种用法

我们在实际开发中经常使用header()实现一些功能&#xff0c;这篇文章介绍关于header()的7中用法&#xff0c;需要的伙伴的开参考一下。 PHP header()的7中用法&#xff1a; 1、跳转页面 可以使用header()实现跳转页面功能。 header(Location:.$url); // $url 跳转页面的地址…...

臻图信息以数字孪生技术推动智慧小区数字化建设

伴随着智慧城市建设进程的加速发展&#xff0c;加速传统小区的管理与服务向智能化升级转型。运用智慧化的管理和服务&#xff0c;利用信息技术和物联网等技术手段&#xff0c;将传统的居住区域与智能设备相结合&#xff0c;实现楼宇、社区设施、服务管理的数字化、网络化、智能…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...