239. Sliding Window Maximum

Problem

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the max sliding window.

Example 1:

  1. Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
  2. Output: [3,3,5,5,6,7]
  3. Explanation: 
  4. Window position                Max
  5. ---------------               -----
  6. [1  3  -1] -3  5  3  6  7       3
  7.  1 [3  -1  -3] 5  3  6  7       3
  8.  1  3 [-1  -3  5] 3  6  7       5
  9.  1  3  -1 [-3  5  3] 6  7       5
  10.  1  3  -1  -3 [5  3  6] 7       6
  11.  1  3  -1  -3  5 [3  6  7]      7

Example 2:

  1. Input: nums = [1], k = 1
  2. Output: [1]

Solution

判断核心思路

  1. 滑动窗口，符合先进先出 FIFO，使用队列
  2. 单调递减队列：来维护维护当前的窗口中最大的数字

理解单调队列

:::info Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
使用这个队列，窗口大小为3 :::

  1. nums[0] = 1 进入队列，得到队列 【1】
  2. nums[1] = 2 进入队列
    1. 判断当前队列的getLast() = 1，小于当前进入队列的值，需要将 1 从队列中移除
      1. 因为 1 已经不可能是这个窗口中最大的数字，它已经不被需要了，毕竟窗口一直向右移动嘛
    2. 此时队列中的数字是 【3】
  3. nums[2] = -1 进入队列
    1. 判断当前队列的getLast() = 3，大于当前进入队列的值，则直接将-1，加进队列
    2. 此时队列中的数字是 【3，-1】
    3. 这就是单调递减队列！
    4. 注意，此时窗口与大小已经是3了，那得到了第一个窗口的最大值，就是队列的头 = 3
  4. nums[3] = -3 进入队列
    1. 判断当前队列的getLast() = -1，大于当前进入队列的值，则直接将-3，加进队列，此时队列 = 【3, -1, -3】
    2. 同时移动窗口的左侧指针，需要把 nums[0] 从窗口中剔除
      1. 考虑到但其实num[0] = 1 并不在队列中 (判断它是都等于队列的getFirst())，所以可以直接忽略
    3. 此时第二个窗口的最大值就是队列的头=3
  5. nums[4] = 5 进入队列
    1. 循环判断当前队列的getLast() ，只要是小于 5 的元素都要被剔除，毕竟我们要维护一个单调递减的队列，所以【3，-1，-3】变成了【5】
    2. 然后剔除num[1]，同样它已经不在队列里了，忽略
    3. 此时第二个窗口的最大值就是队列的头=5
  6. 一次类推，后面的逻辑是重复的，不再赘述