Leetcode 239 滑动窗口最大值

题目信息

LeetoCode地址: . - 力扣（LeetCode）

题目理解

题意是很好理解的，一个固定长度(k)的滑块从一个数组的左端一步一步向右滑，然后挑出滑块盖住的那些数字中最大的，组成的数组就是结果。

难点在于，当滑块移动时，左端的数字会被遗弃，如果遗弃的刚好是最大的数字，则要从剩下的k-1个元素以及右端新覆盖的元素里找到最大的。想要让时间复杂度低，需要找到一种低成本的方式维护这些数字的有序性。这样，即便最大的元素遗弃了，第二大的元素也唾手可得。

如何得到一个单调递减的元素列 array呢？假设当前滑块的左下标是l，右下标是r.

好，我们从下标i=l开始遍历，一开始元素列是空的，直接将i下标存进去。

array = [i]

i递增，来到i+1.此时有两种情况，

1. i+1下标对应的元素比array最后一个元素小
2. i+1下标对应的元素与array最后一个元素一样大
3. i+1下标对应的元素比array最后一个元素大

对第一种和第二种情况，直接将其存入array，因为我们需要的就是单调递减的array。

对第三种情况，如果存入，则违反了单调递减，所以我们要从array尾部一直弹出元素，直到array为空，或者array尾部下标对应的元素比i+1对应的元素要更大。

这里可能有人会想不明白，如果将元素都弹出了，有没有可能找不到最大元素？其实不然，我们在找最大元素时，永远都是从array中取第一个元素，我们永远都会取到最大元素。

发现了嘛，我们是通过单调栈的方式使数组最终有序的，在这个过程中，我们遗弃了那些一定不会用到的元素。

当滑块向右移动时，原理是类似的，array中元素下标小于新l的元素需要从队首弹出，而新r对应的加入的元素需要遵循同样的方式从队尾插入array。

单调栈（单调队列）

在nums长度为l，滑块长度为k的情况下，

时间复杂度: O(l), 滑块至多移动l-k次，每次移动中，元素只会进出queue一次。

额外空间复杂度:O(k), 至多需要k长度的队列存储单调递减的数列。

public int[] maxSlidingWindow(int[] nums, int k) {
        // 题目理解中的array使用 一个双端队列实现
        LinkedList<Integer> queue = new LinkedList<>();
        int length = nums.length;
        int[] res = new int[length-k+1];
        // 对于头k个元素，需要初始化入队操作
        for (int i = 0; i < k; i++) {
            // 递归单调出栈，直到队空或者队尾大于当前元素
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
                queue.pollLast();
            }
            // 插入新队尾元素
            queue.offerLast(i);
        }
        // 此时初始化完成的队列头元素就是第一个最大值
        res[0] = nums[queue.peekFirst()];
        // l 和 r 模拟滑块的左右两端
        int l = 1, r = l+k-1;
        //模拟滑块的移动操作
        while (r < length) {
            // 由于l持续右移，需要将array中队头小于l的元素移除
            while (!queue.isEmpty() && queue.peekFirst() < l) {
                queue.pollFirst();
            }
            // 重复单调出栈以及入栈的操作，保持队列单调递减
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[r]) {
                queue.pollLast();
            }
            queue.offerLast(r);
            res[l] = nums[queue.peekFirst()];
            l++;
            r++;
        }
        return res;
    }