leetcode 239.滑动窗口最大值

题目

思路

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

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

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

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

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

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

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

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

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

代码

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)