滑动窗口最大值

## 1 题目

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

**示例 1：**

```txt
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
[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
```

**示例 2：**

```txt
输入：nums = [1], k = 1
输出：[1]
```

**示例 3：**

```txt
输入：nums = [1,-1], k = 1
输出：[1,-1]
```

**示例 4：**

```txt
输入：nums = [9,11], k = 2
输出：[11]
```

**示例 5：**

```txt
输入：nums = [4,-2], k = 2
输出：[4]
```

**提示：**

* 1 <= nums.length <= 105
* -104 <= nums[i] <= 104
* 1 <= k <= nums.length

## 2 问题分析

1. 这道题不复杂，难点在于**如何在 $O(1)$ 时间算出每个【窗口】中的最大值**，**使得整个算法在线性时间完成**，**在一堆数字中**，**已知最值**，**如果给这堆数添加一个数**，**那么比较一下就可以很快算出最值**，**但如果减少一个数**，**就不一定能很快得到最值了**，**而要遍历所有数重新找最值**。
2. 回到这道题的场景，**每个窗口前进的时候**，**要添加一个数同时减少一个数**，**所以想在 $O(1)$ 的时间得出新的最值**，**就需要【单调队列】这种特殊的数据结构来辅助了**：
   1. 整个单调队列的结构如下：

```java
      class MonotonicQueue {
          //  底层使用双端队列存储数据
          private Deque<Integer> data = new ArrayDeque<>();

// 在队尾添加元素 n
          void push(int n);
          // 返回当前队列中的最大值
          int max();
          // 队头元素如果是 n，删除它
          void pop(int n);
      }
      ```

1. `push(int n)` 方法：
         1. 这个方法中的 $n$**代表我们要添加的元素**。
         2. 我们可以把加入数字的大小**类比于人的体重**，**把前面体重不足的都压扁了**，**直到遇到更大的量级才停住**。
         3. **如果每个元素被加入时都这样操作**，**最终单调队列中的元素就会保持一个单调递减的顺序**，即**队首的元素最大**，**队尾的元素最小**。![无效的图片地址](/media/202111/2021-11-21_2239570.38904421963548796.png)
         4. 该方法的具体实现为：

```java
            void push(int n) {
                while (data.size() != 0 && data.peekLast() < n) {
                    data.pollLast();
                }
                data.offerLast(n);
            }
            ```
      2. `max()` 方法：
         1. **由于每次添加元素时会把小于添加元素的元素弹出**，**因此每次添加元素后的队列都是一个单调递减队列**，**队首的元素即为队列中的最大元素**，**直接返回即可**。
         2. 该方法的具体实现为：

```java
            int max() {
                return data.peekFirst();
            }
            ```
      3. `pop(int n)`：
         1. 这个方法中的 $n$**代表我们要弹出的元素**。
         2. **之所以要判断 `data.peekFirst() == n`**，**是因为我们想删除的对头元素 $n$ 可能已经被【压扁】了**，**这时候就不用删除了**。![无效的图片地址](/media/202111/2021-11-21_2246440.5904891752502391.png)

## 3 参考代码

```java
/**
 * 自定义单调递增队列
 */
class MonotonicQueue {
    //  底层使用双端队列存储数据
    private Deque<Integer> data = new ArrayDeque<>();

/**
     * 插入数据
     * @param n 插入的数据
     */
    void push(int n) {
        while (data.size() != 0 && data.peekLast() < n) {
            //  如果队尾的元素比插入的数据小，则直接将队尾的元素弹出
            data.pollLast();
        }
        //  将元素插入队尾
        data.offerLast(n);
    }

/**
     * 返回队列中的最大值
     * @return  队列中的最大值
     */
    int max() {
        //  由于在插入元素的时候保证双端队列是递增的，因此队首元素即为双端队列中的最大元素
        return data.peekFirst();
    }

/**
     * 弹出元素
     * @param n 弹出的元素
     */
    void pop(int n) {
        //  因为我们想删除的对头元素可能已经在其他元素插入的时候被弹出了，这时候就不用删除了
        if (data.size() != 0 && data.peekFirst() == n) {
            data.pollFirst();
        }
    }
}

/**
 * 239. 滑动窗口最大值
 * @param nums  整数数组
 * @param k 滑动窗口大小
 * @return  滑动窗口中的最大值
 */
public int[] maxSlidingWindow(int[] nums, int k) {
    MonotonicQueue window = new MonotonicQueue();
    int[] res = new int[nums.length - k + 1];
    int index = 0;

for (int i = 0; i < nums.length; i++) {
        if (i < k - 1) {
            //  先填满窗口的前 k - 1
            window.push(nums[i]);
        } else {
            //  窗口向前滑动
            window.push(nums[i]);
            res[index++] = window.max();
            window.pop(nums[i - k + 1]);
        }
    }

return res;
}
```

## 参考文献

1. [239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum)。
2. [单调队列解题详解](https://leetcode-cn.com/problems/sliding-window-maximum/solution/dan-diao-dui-lie-by-labuladong)。