当前位置:网站首页>【剑指 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;
}
}
边栏推荐
- Five simple ways to troubleshoot with Stace
- 2022年理财有哪些产品?哪些适合新手?
- Performance test process and plan
- [principle and technology of network attack and Defense] Chapter 6: Trojan horse
- PIP related commands
- 高考填志愿规则
- Management by objectives [14 of management]
- Thread pool and singleton mode and file operation
- 云安全日报220707:思科Expressway系列和网真视频通信服务器发现远程攻击漏洞,需要尽快升级
- 不能忽略的现货白银短线操作小技巧
猜你喜欢
Classification of regression tests
Backup Alibaba cloud instance OSS browser
debian10系统问题总结
Chapter 2 build CRM project development environment (database design)
Understanding of 12 methods of enterprise management
科学家首次观察到“电子漩涡” 有助于设计出更高效的电子产品
String type, constant type and container type of go language
Mobile app takeout ordering personal center page
3分钟学会制作动态折线图!
What skills can you master to be a "master tester" when doing software testing?
随机推荐
Tips of this week 135: test the contract instead of implementation
Using stored procedures, timers, triggers to solve data analysis problems
How to open an account for wealth securities? Is it safe to open a stock account through the link
Mobile app takeout ordering personal center page
持续测试(CT)实战经验分享
Unlike the relatively short-lived industrial chain of consumer Internet, the industrial chain of industrial Internet is quite long
Introduction de l'API commune de programmation de socket et mise en œuvre de socket, select, Poll et epoll
Hash, bitmap and bloom filter for mass data De duplication
4种常见的缓存模式,你都知道吗?
Chapter 3 business function development (safe exit)
Yearning-SQL审核平台
元宇宙带来的创意性改变
万字保姆级长文——Linkedin元数据管理平台Datahub离线安装指南
Chapter 2 build CRM project development environment (database design)
What is the general yield of financial products in 2022?
sqlite sql 异常 near “with“: syntax error
pip相关命令
Chapter 3 business function development (user login)
CVPR 2022丨学习用于小样本语义分割的非目标知识
『HarmonyOS』DevEco的下载安装与开发环境搭建