leetcode 239.滑动窗口最大值

本文主要是介绍leetcode 239.滑动窗口最大值，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

思路

这是单调队列的经典题目。

最基本思路就是（拿窗口大小为3说明）：

从队列中已经有三个元素开始。先要pop掉第一个元素，然后再push进新的元素，最后返回这三个元素中最大的那一个。

pop和push操作都很简单，那么怎么返回三个元素最大的那一个呢？最简单的就是暴力法，遍历一遍窗口，找到最大值返回。但我们这里不用。

我们用单调队列的方法，在这个方法中，我们把每个窗口的最大值放在最前面，这样直接通过peek()返回就行了。

我们自己定义一个MyQueue类，重写里面的add和poll方法。

add: 因为我们要让队头元素最大，所以获得一个新元素后，我们要依次和它前面的元素进行比较，如果小于的话，就添到队尾。如果大于的话，就将该元素pop掉，继续比较，直到遇到小于的数，添加进去。

poll:随着滑动窗口的移动，每次都会移除一个元素，当要移除的元素正好是队头元素时，则把队头元素pop掉。else,则不需要操作，因为在add的时候就会移除。

理解起来有点困难，其实只要看看代码，自己手动模拟下就明白了。这里用上代码随想录的动画图帮助理解。
239.滑动窗口最大值-2

代码

import java.util.Deque;
import java.util.LinkedList;//leetcode submit region begin(Prohibit modification and deletion)
class MyQueue {Deque<Integer> deque = new LinkedList<>();void poll(int val) {if (val == deque.peek()) {deque.poll();}}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) {int len = nums.length - k + 1; //这表示有几个窗口int[] res = new int[len];int num = 0;//自定义队列MyQueue myQueue = new MyQueue();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;}
}
//leetcode submit region end(Prohibit modification and deletion)