Java 滑动窗口最大值的实现

Java 滑动窗口最大值的实现

一、题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

二、单调队列解析

题目让求随着滑动窗口的滑动，返回窗口覆盖范围的最大值

该题不适合优先级队列，因为采用大顶堆存放k个数字，可以知道此时的最大值，但是窗口是滑动的MrbcqpMC，大顶堆每次只能弹出最大值，无法移除其他值，即无法用大顶堆维护滑动窗口里的值。

所以采用队列维护，随着窗口的移动，队列先进先出

此时对队列的要求是，队列首位为最大值，整个队列呈递减

例如：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 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]);

//记录对应的最大值

resMrbcqpMC[num++] = myQueue.peek();

}

return res;

}

}

四、总结

该题利用了单调队列，需要自己定义入队出队规则

入队：保持队首元素始终最大，同时队内维护窗口的大小个元素，呈现递减

出队：判断当前元素是否入队，在队内，再随着窗口的滑动执行出队操作

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。