【LeetCode】239. 滑动窗口最大值（困难）——代码随想录算法训练营Day13

题目链接：239. 滑动窗口最大值

题目描述

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

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

示例 1：

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

输入：nums = [1], k = 1

输出：[1]

提示：

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

文章讲解：代码随想录

视频讲解：单调队列正式登场！| LeetCode：239. 滑动窗口最大值_哔哩哔哩_bilibili

题解1：单调队列

思路：可以想到用一个队列来存储当前滑动窗口中的元素，每次弹出队首的元素，从队尾插入新元素，求取队列中元素的最大值。因此可以构建一个单调队列，队列中的元素单调递减，队首的元素为最大值。本题中我们只需保持队列是单调递减的，并不需要维护滑动窗口中的所有元素。

下面是根据本题内容建立的一个单调队列所需要的3个方法：

• 入队操作：判断当前队尾元素是否比当前要插入的元素小，如果比当前要插入的元素小，就从队尾删除这个元素，并重复这个过程。最后从队尾插入当前要插入的元素，这样这个元素前面的所有元素都比当前元素大，而前面删除的元素因为小于当前元素，也不需要维护，即维持了队列的单调性。
• 出队操作：判断当前队列最大值（即队首元素）是否为要出队的元素，如果是，弹出队首元素。如果不是，说明之前某个元素入队时因为大于这个元素，已经将其弹出了。
• 获得队列中元素的最大值：即返回队首元素。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    function MyQueue() {
        this.queue = [];
        // 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
        // 这样就保持了队列里的数值是单调从大到小的了。
        this.push = function (val) {
            while (this.queue.length > 0 && this.queue[this.queue.length - 1] < val) {
                this.queue.pop();
            }
            this.queue.push(val);
        };
        // 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
        this.pop = function (val) {
            if (this.queue.length > 0 && this.queue[0] === val) {
                this.queue.shift();
            }
        };
        // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
        this.front = function () {
            return this.queue[0];
        }
    }

    const res = [];
    const myQue = new MyQueue();
    for (let i = 0; i < k; i++) {
        myQue.push(nums[i]);
    }
    res.push(myQue.front());
    for (let i = k; i < nums.length; i++) {
        myQue.pop(nums[i - k]);
        myQue.push(nums[i]);
        res.push(myQue.front());
    }
    return res;
};

分析：时间复杂度为 O(n)，空间复杂度为 O(k)。

收获

学习了根据题目内容构建单调队列思想，对于不同的题目，需要针对构建不同的单调队列。