滑动窗口(单调队列维护窗口)-acwing
题目:
154. 滑动窗口 - AcWing题库


代码(删除队列窗口多余的=>单调队列)
判断最值是否滑出窗口可以放在 入队的后面。
但是,判断,准备入队元素比前面小,要从队尾出队,放在入队前。
总之,是否滑出窗口在最值输出前操作完就行。
单调队列是用来维护当前窗口的(主要是多余的删去了)
- 多余值队尾出队(因为要将当前最小的输出出去,前面更大的都要队尾出去)
- 入队
- 将滑出窗口的索引队头出队
- 输出队头索引的值
从最小值输出开始做:
队列维护窗口的最小值的索引。每次滑动窗口,输出队头索引的数组a值。
#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
int n, k;
int q[N], a[N];int main() {cin >> n >> k;for(int i = 0; i < n; i ++) cin >> a[i];int hh = 0, tt = -1;for(int i = 0; i < n; i ++) {if(hh<=tt && q[hh]<i-k+1) hh ++; // 滑出去了while(hh<=tt && a[q[tt]]>=a[i]) tt--; //前面的大于后面的,去掉前面的q[++tt] = i; //索引入队if(i>=k-1) cout << a[q[hh]] << " "; // 从遍历完第一个窗口开始输出栈顶}puts("");hh = 0, tt = -1;for(int i = 0; i < n; i ++) {if(hh<=tt && q[hh]<i-k+1) hh ++;while(hh<=tt && a[q[tt]]<=a[i]) tt --;q[++tt] = i;if(i>=k-1) cout << a[q[hh]] << " ";}puts("");return 0;
}
代码(使用deque双端队列存窗口最值)
#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
int a[N];
int main() {int n, k;cin >> n >> k;for(int i = 0; i < n; i ++) cin >> a[i];deque<int> q;for(int i = 0; i < n; i ++) {while(q.size() && q.back() > a[i]) q.pop_back();q.push_back(a[i]);//窗口滑动最小值出去了if(i>=k && q.front() == a[i-k]) q.pop_front();if(i>=k-1) cout << q.front() << " ";}puts("");q.clear();for(int i = 0; i < n; i ++) {while(q.size() && q.back() < a[i]) q.pop_back();q.push_back(a[i]);if(i>=k-1 && q.front() == a[i-k]) q.pop_front();if(i>=k-1) cout << q.front() << " ";}puts("");return 0;
}相关文章:
滑动窗口(单调队列维护窗口)-acwing
题目: 154. 滑动窗口 - AcWing题库 代码(删除队列窗口多余的>单调队列) 判断最值是否滑出窗口可以放在 入队的后面。 但是,判断,准备入队元素比前面小,要从队尾出队,放在入队前。 总之&a…...
ALB搭建
ALB: 多级分发、消除单点故障提升应用系统的可用性(健康检查)。 海量微服务间的高效API通信。 自带DDoS防护,集成Web应用防火墙 配置: 1.创建ECS实例 2.搭建应用 此处安装的LNMP 3.创建应用型负载均衡ALB实例 需要创建服务关联角…...
c# 动态lambda实现二级过滤(支持多种参数类型和模糊查询)
效果 调用方法 实体类(可以根据需求更换) public class ToolStr50 {public bool isSelected { get; set; }public string toolStr1 { get; set; }public string toolStr2 { get; set; }public string toolStr3 { get; set; }public string toolStr4 { …...
第J5周:DenseNet+SE-Net实战
🍨 本文为🔗365天深度学习训练营 中的学习记录博客🍖 原作者:K同学啊 任务: ●1. 在DenseNet系列算法中插入SE-Net通道注意力机制,并完成猴痘病识别 ●2. 改进思路是否可以迁移到其他地方呢 ●3. 测试集acc…...
Intern大模型训练营(五):书生大模型全链路开源体系笔记
观看视频,可以比较详细地了解到书生大模型全链路开源体系。 其中有几个印象比较深的点: 这张图讲述了书生浦语大模型开源的发展史,同时与主流的llama和Chatgpt模型进行比较,可以看出在参数上,InterLM在努力追赶甚至超…...
聚观早报 | 比亚迪腾势D9登陆泰国;苹果 iOS 18.2 将发布
聚观早报每日整理最值得关注的行业重点事件,帮助大家及时了解最新行业动态,每日读报,就读聚观365资讯简报。 整理丨Cutie 11月5日消息 比亚迪腾势D9登陆泰国 苹果 iOS 18.2 将发布 真我GT7 Pro防尘防水细节 小米15 Ultra最快明年登场 …...
微信小程序开发,诗词鉴赏app,诗词搜索实现(三)
微信小程序开发,诗词鉴赏app(一): https://blog.csdn.net/jky_yihuangxing/article/details/143501681微信小程序开发,诗词鉴赏app,诗词推荐实现(二):https://blog.csdn.net/jky_yih…...
Kotlin 协程使用及其详解
Kotlin协程,好用,但是上限挺高的,我一直感觉自己就处于会用,知其然不知其所以然的地步。 做点小总结,比较浅显。后面自己再继续补充吧。 一、什么是协程? Kotlin 协程是一种轻量级的并发编程方式&#x…...
计算机组成原理--三章四章
这里写目录标题 第三章:存储系统3.1 存储系统基本概念引入存储器的层次结构简介产品 存储器的分类按层次分类按照介质分类按照存取方式分类按照信息的可更改性按照信息的可保护性 存储器的性能指标存储容量单位成本存储速度 总结 3.2主存储器的基本组成半导体元器件…...
单片机工程使用链接优化-flto找不到定义_链接静态库
IDE: CLion HOST: Windows 11 MinGW:x86_64-14.2.0-release-posix-seh-ucrt-rt_v12-rev0 GCC: arm-gnu-toolchain-13.3.rel1-mingw-w64-i686-arm-none-eabi 示例工程:https://github.com/ichliebedich-DaCapo/STM…...
UniTask/Unity的PlayerLoopTiming触发顺序
开始尝试在项目中使用UniTask,发现其中的UniTask.Yield确实很好用,还可以传入PlayerLoopTiming来更细致的调整代码时机,不过平常在Mono中接触的只有Awake,Start,Update等常用Timing,其他的就没怎么接触了&a…...
【报错记录】Steam迁移(移动)游戏报:移动以下应用的内容失败:XXX: 磁盘写入错误
前言 由于黑神话悟空,导致我的2TB的SSD系统盘快满了,我又买了一块4TB的SSD用来存放游戏,我就打算把之前C盘里的游戏移动到D盘,结果Steam移动游戏居然报错了,报的还是“磁盘写入错误”,如下图所示ÿ…...
C 语言学习-04【结构化程序设计】
1、单分支结构语句 用单分支结构进行奇偶判断: #include <stdio.h>int main() {int num;printf("Please enter an integer: ");scanf("%d", &num);if (num % 2 ! 0) {printf("%d is odd! \n", num);}if (num % 2 0) {prin…...
机器视觉:轮廓匹配算法原理
轮廓匹配的模板变量主要包括模板图像(Template)和待检测图像(Source Image) 在轮廓匹配中,模板变量主要包括一下几个关键部分: 模板图像(Template):这是进行匹配的…...
动力商城-02 环境搭建
1.父工程必须满足:1.1删除src目录 1.2pom 2.依赖继承 //里面的依赖,后代无条件继承<dependencies></dependencies>//里面的依赖,后代想要继承,得自己声明需要使用,可以不写版本号,自动继承&l…...
【react】Redux基础用法
1. Redux基础用法 Redux 是一个用于 JavaScript 应用的状态管理库,它不依赖于任何 UI库,但常用于与 React 框架配合使用。它提供了一种集中式的状态管理方式,将应用的所有状态保存在一个单一的全局 Store(存储)中&…...
使用Python分析股票价格数据并计算移动平均线的实用指南
使用Python分析股票价格数据并计算移动平均线的实用指南 在金融市场中,移动平均线(Moving Average, MA)是一种常用的技术分析工具,用于平滑价格数据,帮助投资者识别趋势。本文将详细介绍如何使用Python分析股票价格数据,并计算移动平均线。我们将通过一个实际的案例来演…...
如何解决FPS低的问题?代码优化方法有哪些?
如果你是一名游戏开发者,或者对电脑性能有所追求的用户,那么你一定遇到过帧率(FPS)低的问题。帧率低会导致游戏卡顿、画面不流畅等问题,极大地影响了用户体验。本文将从代码层面探讨FPS低的原因,并提供一些…...
QT信号和槽与自定义的信号和槽
QT信号和槽与自定义的信号和槽 1.概述 这篇文章介绍下QT信号和槽的入门知识,通过一个案例介绍如何创建信号和槽,并调用他们。 2.信号和槽使用 下面通过点击按钮关闭窗口的案例介绍如何使用信号和槽。 创建按钮 在widget.cpp文件中创建按钮代码如下 …...
LC:二分查找——杂记
文章目录 268. 丢失的数字162. 寻找峰值 268. 丢失的数字 LC将此题归类为二分查找,并且为简单题,下面记一下自己对这道题目的思考。 题目链接:268.丢失的数字 第一次看到这个题目,虽然标注的为简单,但肯定不能直接排…...
【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
scikit-learn机器学习
# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...
Vue ③-生命周期 || 脚手架
生命周期 思考:什么时候可以发送初始化渲染请求?(越早越好) 什么时候可以开始操作dom?(至少dom得渲染出来) Vue生命周期: 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...
ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
密码学基础——SM4算法
博客主页:christine-rr-CSDN博客 专栏主页:密码学 📌 【今日更新】📌 对称密码算法——SM4 目录 一、国密SM系列算法概述 二、SM4算法 2.1算法背景 2.2算法特点 2.3 基本部件 2.3.1 S盒 2.3.2 非线性变换 编辑…...
轻量级Docker管理工具Docker Switchboard
简介 什么是 Docker Switchboard ? Docker Switchboard 是一个轻量级的 Web 应用程序,用于管理 Docker 容器。它提供了一个干净、用户友好的界面来启动、停止和监控主机上运行的容器,使其成为本地开发、家庭实验室或小型服务器设置的理想选择…...
