239. 滑动窗口最大值

leetcode链接：
https://leetcode.cn/problems/sliding-window-maximum/

题目分析

输出数组的 长度为 数组长度 - 滑动窗口长度 + 1

方法一： 将k个数值放入到一个数组中，通过相关工具来求取其中的最大值。

方案一

最终结果，运行超时。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        int[] result = new int[nums.length - k + 1];
        Integer[] numK = new Integer[k];

        for (int i = 0; i < k; i++) {
            numK[i] = nums[i];
        }

        int max = (int) Collections.max(Arrays.asList(numK));
        result[0] = max;

        for (int i = 1; i < result.length; i++) {
            numK[(i - 1) % k] = nums[i + k - 1];
            result[i] = (int) Collections.max(Arrays.asList(numK));
        }

        return result;
    }
}

结果

运行失败:
Time Limit Exceeded
37 / 51 个通过测试用例

分析

此处的问题主要是在求取最大值方面，直接使用工具类的时间复杂度太高。

方案二

使用队列还代替数组，记录最大值所在的位置，判断最大值所在的id位置，以此来减少进行排序的次数。但是此程序在极端情况下的时间复杂度为 n * k

最终结果：运行超时。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        int[] result = new int[nums.length - k + 1];
        Deque deque = new LinkedList<Integer>();
        int max = nums[0], maxId = 0;

        for (int i = 0; i < k; i++) {
            deque.offer(nums[i]);
            if (nums[i] >= max) {
                max = nums[i];
                maxId = i;
            }
        }

        result[0] = max;

        for (int i = 1; i < result.length; i++) {
            deque.poll();
            deque.offer(nums[i + k - 1]);

            if (nums[i + k - 1] > max) {
                max = nums[i + k - 1];
                maxId = i + k - 1;
            } else {
                if (maxId < i) {
                    max = (int) deque.peek();
                    for (int j = 0; j < k; j++) {
                        Integer poll = (Integer) deque.poll();
                        if (poll >= max) {
                            max = poll;
                            maxId = i + j;
                        }
                        deque.offer(poll);
                    }
                }
            }
            result[i] = max;
        }

        return result;
    }
}

结果

运行失败:
Time Limit Exceeded
46 / 51 个通过测试用例

分析

第 47 个用例就是直接触及到了上述方案的极端情况，所有输入的数据都是按照降序进行排列的，每移动一步，就要去循环一次找其 滑动窗口 的最大值，最终导致时间超时。

官方题解

https://leetcode.cn/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/

优先队列

利用优先队列对加入队列的数值进行排序的属性，来实现动态的排序，其排序的时间复杂度为 O(log n)

Java PriorityQueue（优先队列）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.poll();
            }
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：单调队列

动画演示单调队列：
https://leetcode.cn/problems/sliding-window-maximum/solution/dong-hua-yan-shi-dan-diao-dui-lie-239hua-hc5u/

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()];
        for (int i = k; i < n; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/sliding-window-maximum/solution/hua-dong-chuang-kou-zui-da-zhi-by-leetco-ki6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

自行编写的相关代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {

        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<Integer>();

        for (int i = 0; i < k; i++) {
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i);
        }

        result[0] = nums[deque.peekFirst()];

        for (int i = 1; i <= nums.length - k; i++) {
            if (deque.peekFirst() < i) {
                deque.pollFirst();
            }

            while (!deque.isEmpty() && nums[i + k - 1] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.offerLast(i + k - 1);

            result[i] = nums[deque.peekFirst()];
        }

        return result;
    }
}

解答成功:
执行耗时:31 ms,击败了56.34% 的Java用户
内存消耗:58.1 MB,击败了60.31% 的Java用户