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

滑动窗口(单调队列维护窗口)-acwing

题目:

154. 滑动窗口 - AcWing题库

代码(删除队列窗口多余的=>单调队列)

判断最值是否滑出窗口可以放在 入队的后面。

但是,判断,准备入队元素比前面小,要从队尾出队,放在入队前。

总之,是否滑出窗口在最值输出前操作完就行。

单调队列是用来维护当前窗口的(主要是多余的删去了)

  1. 多余值队尾出队(因为要将当前最小的输出出去,前面更大的都要队尾出去)
  2. 入队
  3. 将滑出窗口的索引队头出队
  4. 输出队头索引的值

从最小值输出开始做:

队列维护窗口的最小值的索引。每次滑动窗口,输出队头索引的数组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

题目&#xff1a; 154. 滑动窗口 - AcWing题库 代码&#xff08;删除队列窗口多余的>单调队列&#xff09; 判断最值是否滑出窗口可以放在 入队的后面。 但是&#xff0c;判断&#xff0c;准备入队元素比前面小&#xff0c;要从队尾出队&#xff0c;放在入队前。 总之&a…...

ALB搭建

ALB: 多级分发、消除单点故障提升应用系统的可用性&#xff08;健康检查&#xff09;。 海量微服务间的高效API通信。 自带DDoS防护&#xff0c;集成Web应用防火墙 配置&#xff1a; 1.创建ECS实例 2.搭建应用 此处安装的LNMP 3.创建应用型负载均衡ALB实例 需要创建服务关联角…...

c# 动态lambda实现二级过滤(支持多种参数类型和模糊查询)

效果 调用方法 实体类&#xff08;可以根据需求更换&#xff09; 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实战

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 任务&#xff1a; ●1. 在DenseNet系列算法中插入SE-Net通道注意力机制&#xff0c;并完成猴痘病识别 ●2. 改进思路是否可以迁移到其他地方呢 ●3. 测试集acc…...

Intern大模型训练营(五):书生大模型全链路开源体系笔记

观看视频&#xff0c;可以比较详细地了解到书生大模型全链路开源体系。 其中有几个印象比较深的点&#xff1a; 这张图讲述了书生浦语大模型开源的发展史&#xff0c;同时与主流的llama和Chatgpt模型进行比较&#xff0c;可以看出在参数上&#xff0c;InterLM在努力追赶甚至超…...

聚观早报 | 比亚迪腾势D9登陆泰国;苹果 iOS 18.2 将发布

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 11月5日消息 比亚迪腾势D9登陆泰国 苹果 iOS 18.2 将发布 真我GT7 Pro防尘防水细节 小米15 Ultra最快明年登场 …...

微信小程序开发,诗词鉴赏app,诗词搜索实现(三)

微信小程序开发&#xff0c;诗词鉴赏app&#xff08;一&#xff09;&#xff1a; https://blog.csdn.net/jky_yihuangxing/article/details/143501681微信小程序开发&#xff0c;诗词鉴赏app&#xff0c;诗词推荐实现&#xff08;二&#xff09;:https://blog.csdn.net/jky_yih…...

Kotlin 协程使用及其详解

Kotlin协程&#xff0c;好用&#xff0c;但是上限挺高的&#xff0c;我一直感觉自己就处于会用&#xff0c;知其然不知其所以然的地步。 做点小总结&#xff0c;比较浅显。后面自己再继续补充吧。 一、什么是协程&#xff1f; Kotlin 协程是一种轻量级的并发编程方式&#x…...

计算机组成原理--三章四章

这里写目录标题 第三章&#xff1a;存储系统3.1 存储系统基本概念引入存储器的层次结构简介产品 存储器的分类按层次分类按照介质分类按照存取方式分类按照信息的可更改性按照信息的可保护性 存储器的性能指标存储容量单位成本存储速度 总结 3.2主存储器的基本组成半导体元器件…...

单片机工程使用链接优化-flto找不到定义_链接静态库

IDE&#xff1a; CLion HOST&#xff1a; Windows 11 MinGW&#xff1a;x86_64-14.2.0-release-posix-seh-ucrt-rt_v12-rev0 GCC&#xff1a; arm-gnu-toolchain-13.3.rel1-mingw-w64-i686-arm-none-eabi 示例工程&#xff1a;https://github.com/ichliebedich-DaCapo/STM…...

UniTask/Unity的PlayerLoopTiming触发顺序

开始尝试在项目中使用UniTask&#xff0c;发现其中的UniTask.Yield确实很好用&#xff0c;还可以传入PlayerLoopTiming来更细致的调整代码时机&#xff0c;不过平常在Mono中接触的只有Awake&#xff0c;Start&#xff0c;Update等常用Timing&#xff0c;其他的就没怎么接触了&a…...

【报错记录】Steam迁移(移动)游戏报:移动以下应用的内容失败:XXX: 磁盘写入错误

前言 由于黑神话悟空&#xff0c;导致我的2TB的SSD系统盘快满了&#xff0c;我又买了一块4TB的SSD用来存放游戏&#xff0c;我就打算把之前C盘里的游戏移动到D盘&#xff0c;结果Steam移动游戏居然报错了&#xff0c;报的还是“磁盘写入错误”&#xff0c;如下图所示&#xff…...

C 语言学习-04【结构化程序设计】

1、单分支结构语句 用单分支结构进行奇偶判断&#xff1a; #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…...

机器视觉:轮廓匹配算法原理

轮廓匹配的模板变量主要包括模板图像&#xff08;Template&#xff09;和待检测图像&#xff08;Source Image&#xff09; 在轮廓匹配中&#xff0c;模板变量主要包括一下几个关键部分&#xff1a; ‌模板图像&#xff08;Template&#xff09;‌&#xff1a;这是进行匹配的…...

动力商城-02 环境搭建

1.父工程必须满足&#xff1a;1.1删除src目录 1.2pom 2.依赖继承 //里面的依赖&#xff0c;后代无条件继承<dependencies></dependencies>//里面的依赖&#xff0c;后代想要继承&#xff0c;得自己声明需要使用&#xff0c;可以不写版本号&#xff0c;自动继承&l…...

【react】Redux基础用法

1. Redux基础用法 Redux 是一个用于 JavaScript 应用的状态管理库&#xff0c;它不依赖于任何 UI库&#xff0c;但常用于与 React 框架配合使用。它提供了一种集中式的状态管理方式&#xff0c;将应用的所有状态保存在一个单一的全局 Store&#xff08;存储&#xff09;中&…...

使用Python分析股票价格数据并计算移动平均线的实用指南

使用Python分析股票价格数据并计算移动平均线的实用指南 在金融市场中,移动平均线(Moving Average, MA)是一种常用的技术分析工具,用于平滑价格数据,帮助投资者识别趋势。本文将详细介绍如何使用Python分析股票价格数据,并计算移动平均线。我们将通过一个实际的案例来演…...

如何解决FPS低的问题?代码优化方法有哪些?

如果你是一名游戏开发者&#xff0c;或者对电脑性能有所追求的用户&#xff0c;那么你一定遇到过帧率&#xff08;FPS&#xff09;低的问题。帧率低会导致游戏卡顿、画面不流畅等问题&#xff0c;极大地影响了用户体验。本文将从代码层面探讨FPS低的原因&#xff0c;并提供一些…...

QT信号和槽与自定义的信号和槽

QT信号和槽与自定义的信号和槽 1.概述 这篇文章介绍下QT信号和槽的入门知识&#xff0c;通过一个案例介绍如何创建信号和槽&#xff0c;并调用他们。 2.信号和槽使用 下面通过点击按钮关闭窗口的案例介绍如何使用信号和槽。 创建按钮 在widget.cpp文件中创建按钮代码如下 …...

LC:二分查找——杂记

文章目录 268. 丢失的数字162. 寻找峰值 268. 丢失的数字 LC将此题归类为二分查找&#xff0c;并且为简单题&#xff0c;下面记一下自己对这道题目的思考。 题目链接&#xff1a;268.丢失的数字 第一次看到这个题目&#xff0c;虽然标注的为简单&#xff0c;但肯定不能直接排…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...