🚩传送门：牛客题目
力扣题目

题目

给定一个数组 [NC]82. 滑动窗口的最大值 - 图1 和滑动窗口的大小 [NC]82. 滑动窗口的最大值 - 图2，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值

  1.          ---------------                     -----

[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

要求：空间复杂度 [NC]82. 滑动窗口的最大值 - 图3，时间复杂度 [NC]82. 滑动窗口的最大值 - 图4 。

解题思路：优先队列

对于本题而言，初始时，我们将数组 [NC]82. 滑动窗口的最大值 - 图5 的前 [NC]82. 滑动窗口的最大值 - 图6 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，因此需要判断是否在窗口中，并将不在窗口中的从优先队列中移除。

如何判断最大值是否在滑动窗口中呢？
为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 ([NC]82. 滑动窗口的最大值 - 图7，表示元素 [NC]82. 滑动窗口的最大值 - 图8 在数组中的下标为 [NC]82. 滑动窗口的最大值 - 图9。对于从左向右遍历下标 [NC]82. 滑动窗口的最大值 - 图10就是滑动窗口的右边界，左边界为[NC]82. 滑动窗口的最大值 - 图11，滑动窗口有效区间下标为[NC]82. 滑动窗口的最大值 - 图12。

复杂度分析

时间复杂度： [NC]82. 滑动窗口的最大值 - 图13 ，其中 [NC]82. 滑动窗口的最大值 - 图14 是数组 [NC]82. 滑动窗口的最大值 - 图15 的长度。

  1.   - 在最坏情况下，数组 ![](https://cdn.nlark.com/yuque/__latex/f3d4a01d5b413725d853a14aa61ab2db.svg#card=math&code=%5Ctext%7Bnums%7D&id=Dw5u1) 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为![](https://cdn.nlark.com/yuque/__latex/d81b5dfb2ef5f685bcd4412c0527e1e4.svg#card=math&code=%5Csmall%20O%28%5Clog%20n%29&id=aJw85) 因此总时间复杂度为![](https://cdn.nlark.com/yuque/__latex/83b3f56f15009125fdb632c54c34e35e.svg#card=math&code=%5Csmall%20O%28n%20%5Clog%20n%29&id=riehw) 。

空间复杂度：[NC]82. 滑动窗口的最大值 - 图16 ，即为优先队列需要使用的空间，在最坏情况下，数组 [NC]82. 滑动窗口的最大值 - 图17 中的元素单调递增，那么最终优先队列中包含了所有元素。

我的代码

  1. class Solution {
  2.     public int[] maxSlidingWindow(int[] nums, int k) {
  3.         int n = nums.length;
  4.         // 按照nums[i]降序,nums[i]相同按照i降序
  5.         PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
  6.             public int compare(int[] pair1, int[] pair2) {
  7.                 return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
  8.             }
  9.         });
  10.         for (int i = 0; i < k; ++i) {
  11.             pq.add(new int[]{nums[i], i});
  12.         }
  13.         int[] ans = new int[n - k + 1];
  14.         ans[0] = pq.peek()[0];
  15.         for (int i = k; i < n; ++i) {
  16.             pq.add(new int[]{nums[i], i});
  17.             // 去除无效的最大值,有效左边界i-k+1
  18.             while (pq.peek()[1] < i - k + 1) {
  19.                 pq.poll();
  20.             }
  21.             // 获取有效最大值
  22.             ans[i - k + 1] = pq.peek()[0];
  23.         }
  24.         return ans;
  25.     }
  26. }

解题思路：单调队列

[NC]82. 滑动窗口的最大值 - 图18
算法流程：
初始化： 双端队列 [NC]82. 滑动窗口的最大值 - 图19 ，结果列表 [NC]82. 滑动窗口的最大值 - 图20，数组长度 [NC]82. 滑动窗口的最大值 - 图21 ；
滑动窗口： 左边界范围 ∈[NC]82. 滑动窗口的最大值 - 图22，右边界范围 ∈[NC]82. 滑动窗口的最大值 - 图23 ；

  1. 依次遍历数组中的元素

  2. 当队列非空时，若当前元素大于队尾元素则队尾元素出队 （用以保持 deque 队首至队尾的递减性）

    **while(!deque.isEmpty() && num[i] >= deque.getLast()) {deque.pollLast();}**

  3. 步骤2 执行完毕，则要么队列为空，要么当前元素小于队尾元素，此时将当前元素添加至队列尾端

    **deque.addLast(num[i]);**

  4. 检查过期值是否为窗口最大值，排除不在窗口内的最大值

  5. 将窗口内的最大值加入答案

复杂度分析

时间复杂度： [NC]82. 滑动窗口的最大值 - 图24 ，该方法需要遍历一次数组所有元素 。

空间复杂度：[NC]82. 滑动窗口的最大值 - 图25 ，该方法使用常数空间 。

我的代码

  1. public class Solution {
  2.     public ArrayList<Integer> maxInWindows(int[] num, int size) {
  3.         // 0. 合法性检测
  4.         if (num == null || num.length == 0 || size == 0 || num.length < size)
  5.             return new ArrayList<Integer>();
  6.         // 1. 定义双端队列
  7.         LinkedList<Integer> deque = new LinkedList<>();
  8.         // 2. 保存结果的数组
  9.         ArrayList<Integer> ans = new ArrayList<>();
  10.         for (int i = 0; i < num.length; i++) {
  11.             // 队列非空,若当前元素大于队尾元素则队尾元素出队
  12.             while (!deque.isEmpty() && deque.getLast() <= num[i]) {
  13.                 deque.pollLast();
  14.             }
  15.             // 队尾添加当前元素（此时队空或者当前元素小于队尾元素）
  16.             deque.addLast(num[i]);
  17.             // 检查过期值是否为窗口最大值
  18.             if (i - size >= 0 && num[i - size] == deque.getFirst())
  19.                 deque.pollFirst();
  20.             // 将窗口最大值加入答案
  21.             if (i >= size - 1) ans.add(deque.getFirst());
  22.         }
  23.         return ans;
  24.     }
  25. }