当前位置: 首页 > 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开发的具体业务和算法才是重…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

A2A JS SDK 完整教程:快速入门指南

目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库&#xff…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...