滑动窗口问题
给定一个大小为 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,数据库优化,包括存储引擎的优化&…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
