当前位置:网站首页>【剑指 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;
}
}
边栏推荐
- 保证接口数据安全的10种方案
- The report of the state of world food security and nutrition was released: the number of hungry people in the world increased to 828million in 2021
- Wireshark analyzes packet capture data * cap
- Nunjuks template engine
- 【demo】循环队列及条件锁实现goroutine间的通信
- socket编程之常用api介绍与socket、select、poll、epoll高并发服务器模型代码实现
- Do you really understand sticky bag and half bag? 3 minutes to understand it
- [answer] if the app is in the foreground, the activity will not be recycled?
- Using stored procedures, timers, triggers to solve data analysis problems
- 2022年理财产品的一般收益率是多少?
猜你喜欢
讨论| 坦白局,工业 AR 应用为什么难落地?
[principles and technologies of network attack and Defense] Chapter 5: denial of service attack
How to clean when win11 C disk is full? Win11 method of cleaning C disk
Download, installation and development environment construction of "harmonyos" deveco
简单几步教你如何看k线图图解
More than 10000 units were offline within ten days of listing, and the strength of Auchan Z6 products was highly praised
Idea completely uninstalls installation and configuration notes
低代码助力企业数字化转型会让程序员失业?
[PaddleSeg源码阅读] PaddleSeg Validation 中添加 Boundary IoU的计算(1)——val.py文件细节提示
【Unity Shader】插入Pass实现模型遮挡X光透视效果
随机推荐
手撕Nacos源码(先撕客户端源码)
不能忽略的现货白银短线操作小技巧
Chapter 3 business function development (user access project)
Mobile pixel bird game JS play code
ICer知识点杂烩(后附大量题目,持续更新中)
Disk storage chain B-tree and b+ tree
[trusted computing] Lesson 11: TPM password resource management (III) NV index and PCR
Thread pool and singleton mode and file operation
[trusted computing] Lesson 13: TPM extended authorization and key management
What are the financial products in 2022? What are suitable for beginners?
[C language] string function
[principle and technology of network attack and Defense] Chapter 6: Trojan horse
Chapter 2 build CRM project development environment (database design)
What is the general yield of financial products in 2022?
List selection JS effect with animation
Taffydb open source JS database
[tpm2.0 principle and Application guide] Chapter 5, 7 and 8
Management by objectives [14 of management]
Test for 3 months, successful entry "byte", my interview experience summary
通过 Play Integrity API 的 nonce 字段提高应用安全性