239. Sliding Window Maximum

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */

题目给我们一个数字数组 nums，以及一个长度为 k 的滑动窗口，滑动窗口会从数组左边滑动到最右边

要求我们返回窗口每次滑动过程中能看到的最大元素

例子：

Input: 
    nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: 
    [3,3,5,5,6,7]
Explanation: 
  Window position                Max
  ---------------               -----
  [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

解题思路

我们如果直接用模拟窗口滑动计算窗口内元素最大值的方式，复杂度会变成 O(nk)，其中 n 是 nums 的长度，k 是滑动窗口的长度

所以这题的核心就是想办法把查找窗口中最大值的复杂度从 k 变成 1

要做到这点，我们要从窗口的移动入手，窗口移动时，其左边界 left 有两种可能：

1. nums[left] 不是上一个窗口的最大值
2. nums[left] 是上一个窗口的最大值

第一种可能好处理，直接忽略即可；第二种可能我们需要重新在新的滑动窗口中找到最大值

所以我们需要维护一个单调递减队列

维护方式就是，当滑动窗口右移的时候，弹出所有比新加入滑动窗口的元素小的元素后，再把新元素加入队列中

拿上面的例子来说：

Window position                Max      Queue
---------------               -----     -----
[1  3  -1] -3  5  3  6  7       3       [3, -1]
 1 [3  -1  -3] 5  3  6  7       3       [3, -1, -3]
 1  3 [-1  -3  5] 3  6  7       5       [5]
 1  3  -1 [-3  5  3] 6  7       5       [5, 3]
 1  3  -1  -3 [5  3  6] 7       6       [6]
 1  3  -1  -3  5 [3  6  7]      7       [7]

可以看到，Queue 中的第一个值，就等于我们要求的最大值

Javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    // monotonic decreasing queue
    const queue = []
    const res = []

    for (let right = 0; right < nums.length; right++) {
        // enqueue
        while(queue.length > 0 && nums[queue[queue.length - 1]] <= nums[right]) {
            queue.pop()
        }
        queue.push(right)

        // dequeue
        const left = right - k + 1
        if(left > queue[0]) {
            queue.shift()
        }
        if(left >=0) {
            res.push(nums[queue[0]])
        }
        console.log(queue)
    }

    return res
};