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

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化

一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一&#xff0c;是基于哈希表的Map接口非同步实现。它允许使用null键和null值&#xff08;但只能有一个null键&#xff09;&#xff0c;并且不保证映射顺序的恒久不变。与Hashtable相比&#xff0c;Hash…...

数据库管理与高可用-MySQL故障排查与生产环境优化

目录 #1.1MySQL单案例故障排查 1.1.1MySQL常见的故障排查 1.1.2MySQL主从故障排查 #2.1MySQL优化 2.1.1硬件方面的优化 2.1.2进程方面的优化 #3.1MySQL存储引擎 3.1.1 MyISAM存储引擎 3.1.2 InnoDB存储引擎 1.1MySQL单案例故障排查 1.1.1MySQL常见的故障排查 &#xff08;1&…...

.Net Framework 4/C# 面向对象编程进阶

一、继承 (一)使用继承 子类可以继承父类原有的属性和方法,也可以增加原来父类不具备的属性和方法,或者直接重写父类中的某些方法。 C# 中使用“:”来表示两个类的继承。子类不能访问父类的私有成员,但是可以访问其公有成员,即只要使用 public 声明类成员,就既可以让一…...

JVM——对象模型:JVM对象的内部机制和存在方式是怎样的?

引入 在Java的编程宇宙中&#xff0c;“Everything is object”是最核心的哲学纲领。当我们写下new Book()这样简单的代码时&#xff0c;JVM正在幕后构建一个复杂而精妙的“数据实体”——对象。这个看似普通的对象&#xff0c;实则是JVM内存管理、类型系统和多态机制的基石。…...