滑动窗口问题
给定一个大小为 n≤106 的数组。
有一个大小为 k的滑动窗口,它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子:
该数组为 [1 3 -1 -3 5 3 6 7],k为 3。
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k,分别代表数组长度和滑动窗口的长度。
第二行有 n个整数,代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出,从左至右,每个位置滑动窗口中的最小值。
第二行输出,从左至右,每个位置滑动窗口中的最大值。
输入样例:
8 3
1 3 -1 -3 5 3 6 7
输出样例:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int q[N],a[N];
int main()
{
int n,k;
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++)
{
while(hh<=tt && i-k+1>q[hh]) hh++;//使窗口向右滑动
while(hh<=tt && a[q[tt]]>=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<' ';
}
cout<<endl;
hh=0,tt=-1;
for(int i=0;i<n;i++)
{
while(hh<=tt && i-k+1>q[hh]) hh++;
while(hh<=tt && a[q[tt]]<=a[i]) tt--;
q[++tt]=i;
if(i>=k-1) cout<<a[q[hh]]<<' ';
}
return 0;
}
相关文章:
滑动窗口问题
给定一个大小为 n≤106 的数组。 有一个大小为 k的滑动窗口,它从数组的最左边移动到最右边。 你只能在窗口中看到 k 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子: 该数组为 [1 3 -1 -3 5 3 6 7],k为 3。 窗口位置最小值最…...
电子合同网页预览盖章效果实现
电子合同在现在应用越来越广,需求也就随之产生。 本篇文章主要记录两种网页盖章效果实现方式,自己记录一下, 也给需要的人提供一点思路和帮助。 效果 目录 JqueryCSS实现 原理 1.设置印章图片并隐藏 2.标记盖章位置元素 3.获取目标元素位…...
棋盘覆盖问题
文章目录 棋盘覆盖程序设计程序分析棋盘覆盖 【问题描述】 在一个2k x 2k ( 即:2^k x 2^k )个方格组成的棋盘中,恰有一个方格与其他方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方…...
[CISCN2023]unzip
[CISCN2023]unzip 环境搭建 1.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title> </head> <body><form method"post" action"1.php" en…...
基于Html5的在线资料库的设计与实现(asp.NET,SQLServer)
在线资料库系统采用.NET开发平台进行开发,开发工具采用Microsoft Visual Studio 2010集成开发环境,后台编程语言采用C#编程语言来进行编程开发,数据库我们采用当下流行的SQL Server 2008数据库管理系统来存放平台中的数据信息,整个…...
【Vue】二:Vue核心处理---计算属性 监视属性
文章目录 1.计算属性示例2. 监听属性3.补充 1.计算属性示例 实际上计算属性与methods中定义方法基本上没有什么区别,只是计算属性基于响应式依赖缓存,只要数据没有发生改变,计算属性从缓存中取值,只有当数据发送改变,才…...
【Web服务器集群】Nginx网站服务
文章目录 一、Nginx 概述1.什么是 Nginx2.Nginx 的特点3.Nginx 应用场景 二、Nginx 服务基础1.编译安装 Nginx 服务1.1 布置环境1.2 安装依赖包1.3 创建运行用户、组1.4 编译安装 2.Nginx 的运行控制2.1 检查配置文件2.2 启动、停止 Nginx2.3 日志分割以及升级 Nginx 服务2.4 添…...
开始第一个vue项目,环境搭建+html项目运行
【用vue.js,通过script标签导入】 1. 搭建vue脚手架 安装node js安装cnpm(淘宝源) 【vue】在windows中搭建vue开发环境(全网最详细)_vue环境搭建_一起来学吧的博客-CSDN博客2a 2. 官网下载地址: 安装 …...
Redis 的数据类型和命令帮助
文章结构 Redis 数据类型1. Redis全局命令(跟key有关系,而跟value无关)2. StringsGetting and setting StringsManaging counters 3. Lists(L)Basic commandsBlocking commands 4. Sets(S)Basic commands 5. Hashes(H)Basic commands 6. Sort…...
【C++11】智能指针
什么是智能指针: 智能指针是一个类,用来存储指向动态分配对象的指针,负责自动释放动态分配的对象,防止堆内存泄漏。动态分配的资源,交给一个类对象去管理,当类对象声明周期结束时,自动调用析构函…...
三、Go的常用命令以及Go的执行原理
Go的执行原理以及Go的命令 一、Go的源码文件 Go 的源码文件分类: 如上图,分为三类: 1、命令源码文件: 声明自己属于 main 代码包、包含无参数声明和结果声明的 main 函数。 命令源码文件被安装以后,GOPATH 如果…...
ESP32 CAM 模块和 OpenCV 的二维码扫描器
概述 该项目是关于使用 ESP32 CAM 模块和 OpenCV 设计的二维码扫描仪或阅读器。我们将使用 ESP32 摄像头模块和 python 库开发一个程序和设备,我们可以用它来扫描二维码。使用 ESP32 CAM,项目变得更便宜。 QR 码现在已经成为我们日常生活的一部分,因为我们几乎在任何地方都…...
多链路传输技术在火山引擎 RTC 的探索和实践
动手点关注 干货不迷路 传统的数据传输方式大多是利用一个链路、选择设备的默认网卡进行传输,使用这种方式实现实时音视频通话时,如果默认网络出现问题(如断网、弱网等),用户的通信就会发生中断或者卡顿,影…...
在Flask中构建API接口
重定向行为 斜杠 以下两个路由的不同之处在于是否使用尾部的斜杠。 第一个路由的URL尾部有一个斜杠,看起来就像一个文件夹,访问一个没有斜杠结尾的URL时,Flask会自动进行重定向,在结尾加上一个斜杠。 第二个路由的URL没有尾部…...
Postgres vs MySQL
主要区别及示例 简而言之,Postgres 和 MySQL 之间的主要区别实际上归结为主索引和辅助索引的实现方式以及数据的存储和更新方式。 让我们进一步探讨这个问题。 但首先... 基础知识 索引是一种数据结构(主要是 B 树),允许通过…...
02.IP地址以及静态路由配置
文章目录 IP地址IP地址分类IPV4地址(32位)IPV4地址的分类特殊IP地址 VLSM --- 可变长子网掩码(子网划分)CLDR --- 无类域间路由(汇总)配置静态路由的基础配置静态路由的拓展配置 IP地址 IP地址分类 IPV4(32位二进制构成) — 点分十进制IPV6(128位二进制构成) — 冒分十六进制…...
GD32(STM32)因为中断问题,导致不能进行程序 正常运行
项目中,之前定时器中断就用了个TIM2,但后来程序优化需要再加一个计数定时器TIM6, TIM_TimeBaseInitTypeDef TIM_TimeBaseStructure; // 开启定时器时钟,即内部时钟CK_INT72M RCC_APB1PeriphClockCmd(RCC_APB1Perip…...
华为OD机试真题B卷 Java 实现【统计字符】,附详细解题思路
一、题目描述 输入一行字符,分别统计出包含英文字母、空格、数字和其它字符的个数。 数据范围:输入的字符串长度满足 1 \le n \le 1000 \1≤n≤1000 。 二、输入描述 输入一行字符串,可以有空格。 三、输出描述 统计其中英文字符&#…...
深入理解设计原则之开闭原则(OCP)
系列文章目录 C高性能优化编程系列 深入理解设计原则系列 深入理解设计模式系列 高级C并发线程编程 OCP:开闭原则 系列文章目录1、开闭原则的定义和解读2、如何理解“对扩展开放,对修改关闭”3、实现开闭原则的方法4、如何在团队协作中保证开闭原则的实…...
【学习随笔】
2022/11/13 HTML :讲完了 css:讲完了 作业:编写登陆界面、整理一下sql优化,对于mybatis不熟练的继续练习 关于MySQL优化的问题? 思路总结:主要考虑数据库优化与SQL语句优化。 1,数据库优化,包括存储引擎的优化&…...
使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
