Java 滑动窗口最大值的实现
作者:南淮北安 时间:2021-09-10 15:34:20
一、题目
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
二、单调队列解析
题目让求随着滑动窗口的滑动,返回窗口覆盖范围的最大值
该题不适合优先级队列,因为采用大顶堆存放k个数字,可以知道此时的最大值,但是窗口是滑动的,大顶堆每次只能弹出最大值,无法移除其他值,即无法用大顶堆维护滑动窗口里的值。
所以采用队列维护,随着窗口的移动,队列先进先出
此时对队列的要求是,队列首位为最大值,整个队列呈递减
例如:1,3,-1,-3,5,3,6,7
初始:1,3,-1,队列存入3,-1,使其保持递减,且首位为此时滑动窗口的最大值
移动到-3,队列:3,-1,-3
移动到5,队列:5
移动到3,队列:5,3
移动到6,队列:6
移动到7,队列:7
所以为了满足要求,需要自定义队列
从示例可以看出,队列没必要维护窗口里所有元素,只需要保证队列首位此时窗口的最大,而且,队列元素为递减,具体看代码
三、代码
import java.util.Deque;
import java.util.LinkedList;
//自定义数组
class MyQueue {
Deque<Integer> deque = new LinkedList<>();
//弹出元素时,比较当前要弹出的数值是否等于队列出口的数值,如果相等则弹出
//同时判断队列当前是否为空
void poll(int val) {
if (!deque.isEmpty() && val == deque.peek()) {
deque.poll();
}
}
//添加元素时,如果要添加的元素大于入口处的元素,就将入口元素弹出
//保证队列元素单调递减
//比如此时队列元素3,1,2将要入队,比1大,所以1弹出,此时队列:3,2
void add(int val) {
while (!deque.isEmpty() && val > deque.getLast()) {
deque.removeLast();
}
deque.add(val);
}
//队列队顶元素始终为最大值
int peek() {
return deque.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 1) {
return nums;
}
int len = nums.length - k + 1;
//存放结果元素的数组
int[] res = new int[len];
int num = 0;
//自定义队列
MyQueue myQueue = new MyQueue();
//先将前k的元素放入队列
for (int i = 0; i < k; i++) {
myQueue.add(nums[i]);
}
res[num++] = myQueue.peek();
for (int i = k; i < nums.length; i++) {
//滑动窗口移除最前面的元素,移除是判断该元素是否放入队列
myQueue.poll(nums[i - k]);
//滑动窗口加入最后面的元素
myQueue.add(nums[i]);
//记录对应的最大值
res[num++] = myQueue.peek();
}
return res;
}
}
四、总结
该题利用了单调队列,需要自己定义入队出队规则
入队:保持队首元素始终最大,同时队内维护窗口的大小个元素,呈现递减
出队:判断当前元素是否入队,在队内,再随着窗口的滑动执行出队操作
来源:https://blog.csdn.net/nanhuaibeian/article/details/117047732
标签:Java,滑动窗口最大值
0
投稿
猜你喜欢
Java分布式事务管理框架之Seata
2023-09-28 11:50:36
Android ViewPager实现页面左右切换效果
2022-12-28 04:49:35
Java读取txt文件中的数据赋给String变量方法
2022-08-04 22:32:19
详解java中的PropertyChangeSupport与PropertyChangeListener
2023-10-20 06:19:27
流读取导致StringBuilder.toString()乱码的问题及解决
2022-12-20 13:34:14
Mybatis plus多租户方案的实战踩坑记录
2023-08-01 05:19:09
C#删除只读文件或文件夹(解决File.Delete无法删除文件)
2022-06-30 15:01:59
详解C++ STL模拟实现forward_list
2023-06-21 02:36:04
关于Android HTML5 audio autoplay无效问题的解决方案
2021-09-22 04:10:30
C#如何使用Task执行异步操作
2023-01-12 03:34:41
C#使用有道ip地址查询接口方法实例详解
2022-10-08 22:07:31
maven无法依赖spring-cloud-stater-zipkin的解决方案
2023-09-12 01:54:51
Java中ShardingSphere分库分表实战
2023-11-24 09:20:37
java 对象参数去空格方式代码实例
2023-11-27 09:49:34
如何在Java SpringBoot项目中配置动态数据源你知道吗
2021-07-23 11:10:08
jstorm源码解析之bolt异常处理方法
2022-08-05 23:12:08
C# 关于爬取网站数据遇到csrf-token的分析与解决
2023-07-25 06:25:39
Bean Searcher配合SpringBoot的使用详解
2022-06-21 23:49:00
C#递归应用之实现JS文件的自动引用
2023-12-09 00:03:52
实例详解Android自定义ProgressDialog进度条对话框的实现
2023-02-18 08:32:40