滑动窗口最大值

[Cosen95]

leetcode: https://leetcode-cn.com/problems/sliding-window-maximum/

[Cosen95]

题目难度hard，涉及到的算法知识有双端队列。

题目描述

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

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

进阶：你能在线性时间复杂度内解决此题吗？

示例:

输入: 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

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= nums.length

思路分析

暴力求解

第一种方法，比较简单。也是大多数同学很快就能想到的方法。

• 遍历数组
• 依次遍历每个区间内的最大值，放入数组中

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    let len = nums.length;
    if(len === 0) return []
    if(k === 1) return nums
    let resArr = []
    for(let i = 0; i <= len - k;i++) {
        let max = Number.MIN_SAFE_INTEGER;
        for(let j = i; j < i + k; j++) {
            max = Math.max(max, nums[j])
        }
        resArr.push(max)
    }
    return resArr;
};

双端队列

这道题还可以用双端队列去解决，核心在于在窗口发生移动时，只根据发生变化的元素对最大值进行更新。

结合上面动图(图片来源)我们梳理下思路：

• 检查队尾元素，看是不是都满足大于等于当前元素的条件。如果是的话，直接将当前元素入队。否则，将队尾元素逐个出队、直到队尾元素大于等于当前元素为止。（这一步是为了维持队列的递减性：确保队头元素是当前滑动窗口的最大值。这样我们每次取最大值时，直接取队头元素即可。）
• 将当前元素入队
• 检查队头元素，看队头元素是否已经被排除在滑动窗口的范围之外了。如果是，则将队头元素出队。（这一步是维持队列的有效性：确保队列里所有的元素都在滑动窗口圈定的范围以内。）
• 排除掉滑动窗口还没有初始化完成、第一个最大值还没有出现的特殊情况。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    // 缓存数组的长度
    const len = nums.length;
    const res = [];
    const deque = [];
    for (let i = 0; i < len; i++) {
        // 队尾元素小于当前元素
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) {
            deque.pop()
        }
        deque.push(i)

        // 当队头元素的索引已经被排除在滑动窗口之外时
        while (deque.length && deque[0] <= i - k) {
            // 队头元素出对
            deque.shift()
        }
        if (i >= k - 1) {
            res.push(nums[deque[0]])
        }
    }
    return res
};