面试题65. 滑动窗口的最大值

2024-05-14 16:38

本文主要是介绍面试题65. 滑动窗口的最大值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

给定一个数组和滑动窗口的大小,找出所有滑动窗口里数值的最大值。例如,如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3,那么一共存在6个滑动窗口:{[2,3,4],2,6,2,5,1}, {2,[3,4,2],6,2,5,1}, {2,3,[4,2,6],2,5,1}, {2,3,4,[2,6,2],5,1}, {2,3,4,2,[6,2,5],1}, {2,3,4,2,6,[2,5,1]},他们的最大值分别为{4,4,6,6,6,5}。

思路1:
暴力求解法,扫描滑动窗口中的每一个数字,并找出其中的最大值。如果滑动窗口的大小为m,则找到窗口内的最大值需要O(k)时间。对于长度为n的数组,总的时间复杂度为O(mn)

思路2:
借助一个辅助队列,从头遍历数组,根据如下规则进行入队列或出队列操作:
0. 如果队列为空,则当前数字入队列
1. 如果当前数字大于队列尾,则删除队列尾,直到当前数字小于等于队列尾,或者队列空,然后当前数字入队列
2. 如果当前数字小于队列尾,则当前数字入队列
3. 如果队列头超出滑动窗口范围,则删除队列头
这样能始终保证队列头为当前的最大值

以这道题为例:
从头开始遍历数组,我们以下标 i 表示遍历到第几个数字
在开始阶段,队列为空,我们把2入队列,此时i = 0;

这里写图片描述

i = 1时,num[1] = 3, 由于3大于队列尾2,所以把2移出队列,把3加入队列;

这里写图片描述

i = 2时,num[2] = 4, 由于4大于3, 所以把3移出队列,把4加入队列,此时滑动窗口刚好经过三个元素,滑动窗口内的最大值就是队列的头元素,也就是4;

这里写图片描述

i = 3时,num[3] = 2, 因为2小于4,所以把2直接加入队列,此时滑动窗口内的最大值仍然为4;

这里写图片描述

i = 4时,num[4] = 6, 6大于2和4,所以把2和4移出队列,把6加入到队列中,此时滑动窗口的最大值为6;

这里写图片描述

i = 5时,num[5] = 2, 因为2小于6,所以把2直接加入队列,此时滑动窗口内的最大值仍然为6;

这里写图片描述

i = 6时,num[6] = 5, 由于5大于2,所以把2移出队列,把5加入队列中,此时滑动窗口内的最大值仍然为6;

这里写图片描述

i = 7时,num[7] = 1, 由于6已经不在滑动窗口中了,所以将6从队列头上删除,此时滑动窗口的最大值为5;

这里写图片描述

遍历结束

那么,如何判断6是否还在滑动窗口中呢,可以通过数组下标进行判断,我们在队列中存储数组的下标而非数值,这样通过判断下标之间的差值是否大于窗口的大小,就可以判断元素是否还在滑动窗口中。

Java 代码如下:

import java.util.*;public class Solution {public ArrayList<Integer> maxInWindows(int[] num, int size) {ArrayList<Integer> result = new ArrayList<>();if(num == null || num.length == 0 || size == 0 || size > num.length) {return result;}LinkedList<Integer> queue = new LinkedList<>();for(int i = 0; i < num.length; i++) {if(!queue.isEmpty()){// 如果队列头元素不在滑动窗口中了,就删除头元素if(i >= queue.peek() + size) { queue.pop();}// 如果当前数字大于队列尾,则删除队列尾,直到当前数字小于等于队列尾,或者队列空while(!queue.isEmpty() && num[i] >= num[queue.getLast()]) {queue.removeLast();}}queue.offer(i); // 入队列// 滑动窗口经过三个元素,获取当前的最大值,也就是队列的头元素if(i + 1 >= size) {result.add(num[queue.peek()]);}}return result;}
}

这篇关于面试题65. 滑动窗口的最大值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/989280

相关文章

荣耀嵌入式面试题及参考答案

在项目中是否有使用过实时操作系统? 在我参与的项目中,有使用过实时操作系统。实时操作系统(RTOS)在对时间要求严格的应用场景中具有重要作用。我曾参与的一个工业自动化控制项目就采用了实时操作系统。在这个项目中,需要对多个传感器的数据进行实时采集和处理,并根据采集到的数据及时控制执行机构的动作。实时操作系统能够提供确定性的响应时间,确保关键任务在规定的时间内完成。 使用实时操作系统的

一些其他面试题

阿里二面:那你来说说定时任务?单机、分布式、调度框架下的定时任务实现是怎么完成的?懵了。。_哔哩哔哩_bilibili 1.定时算法 累加,第二层每一个格子是第一层的总时间400 ms= 20 * 20ms 2.MQ消息丢失 阿里二面:高并发场景下引进消息队列有什么问题?如何保证消息只被消费一次?真是捏了一把汗。。_哔哩哔哩_bilibili 发送消息失败

使用JS/Jquery获得父窗口的几个方法(笔记)

<pre name="code" class="javascript">取父窗口的元素方法:$(selector, window.parent.document);那么你取父窗口的父窗口的元素就可以用:$(selector, window.parent.parent.document);如题: $(selector, window.top.document);//获得顶级窗口里面的元素 $(

zookeeper相关面试题

zk的数据同步原理?zk的集群会出现脑裂的问题吗?zk的watch机制实现原理?zk是如何保证一致性的?zk的快速选举leader原理?zk的典型应用场景zk中一个客户端修改了数据之后,其他客户端能够马上获取到最新的数据吗?zk对事物的支持? 1. zk的数据同步原理? zk的数据同步过程中,通过以下三个参数来选择对应的数据同步方式 peerLastZxid:Learner服务器(Follo

java常用面试题-基础知识分享

什么是Java? Java是一种高级编程语言,旨在提供跨平台的解决方案。它是一种面向对象的语言,具有简单、结构化、可移植、可靠、安全等特点。 Java的主要特点是什么? Java的主要特点包括: 简单性:Java的语法相对简单,易于学习和使用。面向对象:Java是一种完全面向对象的语言,支持封装、继承和多态。跨平台性:Java的程序可以在不同的操作系统上运行,称为"Write once,

专题二_滑动窗口_算法专题详细总结

目录 滑动窗口,引入: 滑动窗口,本质:就是同向双指针; 1.⻓度最⼩的⼦数组(medium) 1.解析:给我们一个数组nums,要我们找出最小子数组的和==target,首先想到的就是暴力解法 1)暴力: 2)优化,滑动窗口: 1.进窗口 2.出窗口 3.更新值 2.⽆重复字符的最⻓⼦串(medium) 1)仍然是暴力解法: 2)优化: 进窗口:hash[s[rig

【Kubernetes】常见面试题汇总(三)

目录 9.简述 Kubernetes 的缺点或当前的不足之处? 10.简述 Kubernetes 相关基础概念? 9.简述 Kubernetes 的缺点或当前的不足之处? Kubernetes 当前存在的缺点(不足)如下: ① 安装过程和配置相对困难复杂; ② 管理服务相对繁琐; ③ 运行和编译需要很多时间; ④ 它比其他替代品更昂贵; ⑤ 对于简单的应用程序来说,可能不

【附答案】C/C++ 最常见50道面试题

文章目录 面试题 1:深入探讨变量的声明与定义的区别面试题 2:编写比较“零值”的`if`语句面试题 3:深入理解`sizeof`与`strlen`的差异面试题 4:解析C与C++中`static`关键字的不同用途面试题 5:比较C语言的`malloc`与C++的`new`面试题 6:实现一个“标准”的`MIN`宏面试题 7:指针是否可以是`volatile`面试题 8:探讨`a`和`&a`

Laravel 面试题

PHP模块 PHP7 和 PHP5 的区别,具体多了哪些新特性? 性能提升了两倍 结合比较运算符 (<=>) 标量类型声明 返回类型声明 try…catch 增加多条件判断,更多 Error 错误可以进行异常处理 匿名类,现在支持通过new class 来实例化一个匿名类,这可以用来替代一些“用后即焚”的完整类定义 …… 了解更多查看文章底部链接 PHP7 新特性 为什么 PHP

【吊打面试官系列-Redis面试题】说说 Redis 哈希槽的概念?

大家好,我是锋哥。今天分享关于 【说说 Redis 哈希槽的概念?】面试题,希望对大家有帮助; 说说 Redis 哈希槽的概念? Redis 集群没有使用一致性 hash,而是引入了哈希槽的概念,Redis 集群有 16384 个哈希槽,每个 key 通过 CRC16 校验后对 16384 取模来决定放置哪个槽, 集群的每个节点负责一部分 hash 槽。