当前位置:网站首页>【剑指 Offer】59 - I. 滑动窗口的最大值
【剑指 Offer】59 - I. 滑动窗口的最大值
2022-07-07 16:36:00 【LuZhouShiLi】
剑指 Offer 59 - I. 滑动窗口的最大值
题目
给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
思路
- 遍历给定数组中的元素,如果队列不为空且当前考察的元素大于等于队尾元素,则将队尾元素移除,直到队列为空或者当前考察元素小于新的队尾元素
- 当队首元素的下标小于滑动窗口的左侧边界Left表示队首元素已经不再属于滑动窗口,将其从队首元素移除
- 由于数组下标从0开始,因此当窗口的右边界right + 1>= k,意味着窗口已经形成。此时队首元素就是该窗口内的最大值。
代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0)
{
return new int[0];
}
// 窗口个数
int[] res = new int[nums.length - k + 1];
LinkedList<Integer> queue = new LinkedList<>();
// 遍历数组中元素, right表示滑动窗口右边界
for(int right = 0; right < nums.length; right++)
{
// 如果队列不为空 并且当前的元素大于或者等于队尾元素 将队尾元素移除
// 直到 队列为空 或者当前的元素小于新的队尾元素
while(!queue.isEmpty() && nums[right] >= nums[queue.peekLast()]){
queue.removeLast();
}
// 存储元素下标
queue.addLast(right);
// 计算窗口左侧边界
int left = right - k + 1;
//当队首元素的下标小于滑动窗口左侧边界Left
// 表示队首元素已经不再滑动窗口内部 将其从队首中移除
if(queue.peekFirst() < left)
{
queue.removeFirst();
}
// 下边从0开始 所以当right + 1 >= k 说明滑动窗口已经形成 队首元素就是窗口的最大值
if(right + 1 >= k)
{
res[left] = nums[queue.peekFirst()];// 将队首元素存储到res中
}
}
return res;
}
}
边栏推荐
- 用存储过程、定时器、触发器来解决数据分析问题
- Tips for short-term operation of spot silver that cannot be ignored
- 行业案例|数字化经营底座助力寿险行业转型
- [demo] circular queue and conditional lock realize the communication between goroutines
- DataSimba推出微信小程序,DataNuza接受全场景考验? | StartDT Hackathon
- 嵌入式C语言程序调试和宏使用的技巧
- [trusted computing] Lesson 13: TPM extended authorization and key management
- Chapter 3 business function development (user access project)
- 开发一个小程序商城需要多少钱?
- Mobile app takeout ordering personal center page
猜你喜欢
A few simple steps to teach you how to see the K-line diagram
回归测试的分类
[4500 word summary] a complete set of skills that a software testing engineer needs to master
Some key points in the analysis of spot Silver
Download, installation and development environment construction of "harmonyos" deveco
CVPR 2022丨学习用于小样本语义分割的非目标知识
ICer知识点杂烩(后附大量题目,持续更新中)
2021年全国平均工资出炉,你达标了吗?
How to clean when win11 C disk is full? Win11 method of cleaning C disk
[principle and technology of network attack and Defense] Chapter 1: Introduction
随机推荐
[trusted computing] Lesson 10: TPM password resource management (II)
通过 Play Integrity API 的 nonce 字段提高应用安全性
PHP面试题 foreach($arr as &$value)与foreach($arr as $value)的用法
小试牛刀之NunJucks模板引擎
debian10系统问题总结
性能测试过程和计划
Test for 3 months, successful entry "byte", my interview experience summary
zdog. JS rocket turn animation JS special effects
五种网络IO模型
上市十天就下线过万台,欧尚Z6产品实力备受点赞
golang 客户端服务端登录
Mobile app takeout ordering personal center page
Summary of evaluation indicators and important knowledge points of regression problems
C语言中匿名的最高境界
Unlike the relatively short-lived industrial chain of consumer Internet, the industrial chain of industrial Internet is quite long
Chapter 2 building CRM project development environment (building development environment)
pip相关命令
How to open an account for wealth securities? Is it safe to open a stock account through the link
同消费互联网的较为短暂的产业链不同,产业互联网的产业链是相当漫长的
Mobile pixel bird game JS play code