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

滑动窗口 AcWing (JAVA)

 给定一个大小为 n≤10^6 的数组。

有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子:

该数组为 [1 3 -1 -3 5 3 6 7],k 为 33。

窗口位置最小值最大值
[1 3 -1] -3 5 3 6 7-13
1 [3 -1 -3] 5 3 6 7-33
1 3 [-1 -3 5] 3 6 7-35
1 3 -1 [-3 5 3] 6 7-35
1 3 -1 -3 [5 3 6] 736
1 3 -1 -3 5 [3 6 7]37

 你的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。

输入格式:

 输入包含两行。

第一行包含两个整数 n和 k,分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数,代表数组的具体数值。

同行数据之间用空格隔开。

输出格式:

输出包含两个。

第一行输出,从左至右,每个位置滑动窗口中的最小值。

第二行输出,从左至右,每个位置滑动窗口中的最大值。

解题思路: 如果朴素的做法,将每次得到的窗口进行遍历找最小值。时间复杂度大概是nk,不出意外是会超时的。如何对其进行优化呢?

首先以数组q[N],作为本题队列,a[N]存入输入的元素。我们知道下标和元素具有一 一对应的关系,所以q[i]不是存入元素所对应的值,而是元素所对应的下标。

 在这里设hh = 0为头指针,tt = - 1为尾指。

首先应该明确窗口的特点:即内部元素的数量在k的时候即可输出最内部最小值和最大值。此后每移动一下就再次输出一次。这恰好哦可以用循环变量i来表示,如下窗口:

[a,b,c,d.....]

0                i             窗口内部元素的数量可用 (i - 0 + 1)来表示,当窗口内数量够k个的时候即可输出,即i - 0 + 1 >= k即 i >= k - 1。

有趣的是当 0~i + 2 中c为最小值的时候,当窗口向右边移动的时候:

[b,c,d,e.....]

1               i + 1         min = c

[c,d,e,f.....]

2              i + 2          min = c

不难看出窗口在移动的时候,最小值仍是c,如果能用队列存入最小值的下标(即q[tt] = 2),那就避免重新遍历窗口的麻烦。那问题来了设立队列只是为了存入一个最小值的吗?这显然不是,如下窗口继续向右移动:

[d,e,f,g.....]

3             i + 3       min =  ?    由此可见如果队列里值只存入c的下标,当窗口不包含c的时候队列内的 q[tt] = 2 也就没用了。

那么需要队列,理想的情况是让队列内存入 最小元素下标,第二小元素下标,第三小元素下标.......

当窗口不再包含最小元素的时候那么就可以在队列内删去了,那么第二小元素就理应成为新的最小元素了,以此类推,队列头部元素一直是符合条件的最小元素下标。

至于如何输出最大值,和上述反着来即可。

理论成立代码如下(未加速版):

import java.util.*;public class Main {public static int N = 1000010;public static void main(String[] args) {Scanner sc  = new Scanner(System.in);int a[] = new int [N];//数组int q[] = new int [N];//队列int n = sc.nextInt();int k = sc.nextInt();for(int i = 0; i < n; i ++) a[i] = sc.nextInt();int hh = 0, tt = -1;//队头,队尾,q[hh]存入最小元素下标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) {if(i == n-1)System.out.println(a[q[hh]]);elseSystem.out.print(a[q[hh]]+" ");  }	    }
//输出最大值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) {if(i == n - 1)System.out.print(a[q[hh]]);elseSystem.out.print(a[q[hh]]+" ");}}}
}

由于最后一个数据过于庞大,时间超时了,想通过,得用如下的加速版:

import java.io.*;
import java.util.*;;
public class Main {public static int N = 1000010;public static void main(String[] args) throws IOException {// TODO Auto-generated method stubScanner sc = new Scanner(new BufferedInputStream(System.in));BufferedWriter sout = new BufferedWriter(new OutputStreamWriter(System.out));int a[] = new int [N];//数组int q[] = new int [N];//队列int n = sc.nextInt();int k = sc.nextInt();for(int i = 0; i < n; i ++) a[i] = sc.nextInt();int hh = 0, tt = -1;//队头,队尾,q[hh]存入最小元素下标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) {sout.write(a[q[hh]]+" ");  }	    }sout.write("\n");//输出最大值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) {sout.write(a[q[hh]]+" ");}}sout.close();sc.close();}}

相关文章:

滑动窗口 AcWing (JAVA)

给定一个大小为 n≤10^6 的数组。 有一个大小为 k 的滑动窗口&#xff0c;它从数组的最左边移动到最右边。 你只能在窗口中看到 k 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子&#xff1a; 该数组为 [1 3 -1 -3 5 3 6 7]&#xff0c;k 为 33。 窗口位置最小值最大…...

vue小案例

vue小案例 组件化编码流程 1.拆分静态组件&#xff0c;按功能点拆分 2.实现动态组件 3.实现交互 文章目录vue小案例组件化编码流程1.父组件给子组件传值2.通过APP组件给子组件传值。3.案例实现4.项目小细节1.父组件给子组件传值 父组件给子组件传值 1.在父组件中写好要传的值&a…...

阅读笔记3——空洞卷积

空洞卷积 1. 背景 空洞卷积&#xff08;Dilated Convolution&#xff09;最初是为解决图像分割的问题而提出的。常见的图像分割算法通常使用池化层来增大感受野&#xff0c;同时也缩小了特征图尺寸&#xff0c;然后再利用上采样还原图像尺寸。特征图先缩小再放大的过程造成了精…...

CSS系统学习总结

目录 CSS边框 CSS背景 CSS3渐变 线性渐变&#xff08;Linear Gradients&#xff09;- 向下/向上/向左/向右/对角方向 语法 线性渐变&#xff08;从上到下&#xff09; 线性渐变&#xff08;从左到右&#xff09; 线性渐变&#xff08;对角&#xff09; 使用角度 使用多…...

阿里一面:你做过哪些代码优化?来一个人人可以用的极品案例

前言 在尼恩读者50交流群中&#xff0c;尼恩经常指导小伙伴改简历。 改简历所涉及的一个要点是&#xff1a; 在 XXX 项目中&#xff0c;完成了 XXX 模块的代码优化 另外&#xff0c;在面试的过程中&#xff0c;面试官也常常喜欢针对提问&#xff0c;来考察候选人对代码质量的追…...

Android NFC 标签读写Demo与历史漏洞概述

文章目录前言NFC基础1.1 RFID区别1.2 工作模式1.3 日常应用NFC标签2.1 标签应用2.2 应用实践2.3 标签预览2.4 前台调度NFC开发3.1 NDEF数据3.2 标签的调度3.3 读写Demo3.4 Demo演示历史漏洞4.1 中继攻击4.2 预览伪造4.3 篡改卡片4.4 其它漏洞总结前言 NFC 作为 Android 手机一…...

亿级高并发电商项目-- 实战篇 --万达商城项目 六(编写角色管理、用户权限(Spring Security认证授权)、管理员管理等模块)

专栏&#xff1a;高并发---前后端分布式 &#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是小童&#xff0c;Java开发工程师&#xff0c;CSDN博客博主&#xff0c;Java领域新星创作者 &#x1f4d5;系列专栏&#xff1a;前端、Java、Java中间件大全、微信小程序、微信…...

博视像元获近5000万元融资,主攻半导体前道及锂电高端部件供应

这两年各大车企与电池厂商都在快速新建产能&#xff0c;尤其上游原材料成本大增&#xff0c;反映到产业链上巨头都在寻求增效&#xff0c;高端制造技术投入也大幅增长。比如这家&#xff0c;高端工业相机提供商「博视像元」近期宣布完成近5000万的天使加轮融资&#xff0c;投资…...

SpringCloud-断路器Hystrix

一、降级使用1、添加依赖<!--hystrix--><dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-netflix-hystrix</artifactId></dependency>2、启动类添加注解EnableCircuitBreakerSpringBoot…...

JavaScript精简笔记

文章目录基础语法函数1.1、函数的使用预解析对象1.1、创建对象基础语法 函数 1.1、函数的使用 函数在使用时分为两步&#xff1a;声明函数和调用函数 ①声明函数 //声明函数 function 函数名(){//函数体代码 }function 是声明函数的关键字,必须小写由于函数一般是为了实现…...

MySQL常用函数汇总

1 MySQL 字符串函数函数描述实例ASCII(s)返回字符串 s 的第一个字符的 ASCII 码。返回 CustomerName 字段第一个字母的 ASCII 码&#xff1a;SELECT ASCII(CustomerName) AS NumCodeOfFirstCharFROM Customers;CHAR_LENGTH(s)返回字符串 s 的字符数返回字符串 RUNOOB 的字符数S…...

100M网口客户电脑插上网线就断线,自己工厂正常,是什么问题导致?

Hqst&#xff08;华强盛科技&#xff09;导读&#xff1a;物联工程师100M网口产品出现客户电脑插上网线就显示断线&#xff0c;无法通信&#xff0c;在自己工厂又正常使用&#xff0c;是什么问题&#xff1f;问&#xff1a;100M 网口&#xff0c; 使用改电路&#xff0c; 产品出…...

从零开始学习无人机 00 硬件配置

遥控器 型号 乐迪Radiolink AT9S Pro 固件更新 对遥控器固件作更新 乐迪Radiolink AT9S Pro 固件更新 光流传感器 型号 思动智能ThoneFlow-3901U 开发文档 Pmw3901光流传感器PX4开发文档 距离传感器 型号 空循环Nooploop TOFSense-F Pro 开发文档 TOFSense-F官方…...

免翻在Chrome上使用新必应(New Bing)聊天机器人

这里不讲如何加入New Bing内测 文章目录免翻使用New Bing用Chrome(非Edge)使用新必应聊天机器人免翻使用New Bing 第一个是免翻&#xff0c;需要一个浏览器插件Header Editor&#xff0c;扩展商店或者百度自行下载安装吧。打开该插件&#xff0c;添加一个规则 为方便填写&…...

LA@特征值和特征向量

文章目录特征值和特征向量例例求解方阵的特征值和特征向量&#x1f388;特征多项式特征方程方阵特征值和特征向量的性质证明推论衍生特征值更一般的转置和特征值其他结论(方阵多项式的特征值与方阵本身特征值的关系)特征向量线性相关性特征值和特征向量 许多定量分析模型中,常常…...

transpose代码学习

论文&#xff1a;TransPose: Keypoint Localization via Transformer Sen Yang Zhibin Quan Mu Nie Wankou Yang* School of Automation, Southeast University, Nanjing 210096, China {yangsenius, 101101872, niemu, wkyang}seu.edu.cn 下载地址&#xff1a;https://arxiv.o…...

【Redis】Redis 常用数据类型操作 ② ( 数据库操作 | 切换数据库 | 查询当前数据库键个数 | 清空当前数据库 | 清空所有数据库 )

文章目录一、Redis 数据库操作1、切换数据库2、查询当前数据库键个数3、清空当前数据库4、清空所有数据库一、Redis 数据库操作 在之前的博客 【Redis】Redis 数据库 安装、配置、访问 ( Redis 简介 | 下载 Redis 安装包 | 安装 Redis 数据库 | 命令行访问 Redis | 使用可视化工…...

最简单的物体识别例子

第一步下载百度EASYDL工具。 网址EasyDL 图像 然后下载本地训练工具包&#xff1a; 本地下载&#xff0c;运行。 首先创建数据集&#xff0c; 完成&#xff0c;创建目标任务。 选择物体检测创建任务 选择训练&#xff0c;将数据集引入 通用型小型设备SDK 选择这个可以本地直…...

指针——“C”

各位CSDN的uu们你们好呀&#xff0c;今天&#xff0c;小雅兰学习的内容是指针&#xff0c;这次只会讲一些很简单的知识点&#xff0c;更详细的指针知识会在以后的博客中逐步剖析清楚&#xff0c;那么现在&#xff0c;就让我们进入指针的世界吧 指针是什么 指针和指针类型 野指…...

学习 Linux 内核书籍推荐

原文链接&#xff0c;欢迎关注&#xff1a; 你为什么学习 Linux 内核&#xff1f; - CodeAllen的回答 - 知乎 https://www.zhihu.com/question/31369673/answer/2894981254 主要是工作需要&#xff0c;其实对于我自己的工作来说&#xff0c;在Linux开发的具体业务和算法才是重…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...