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

发布时间:2024年01月22日

题目链接: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)。

收获

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

文章来源:https://blog.csdn.net/m0_57521762/article/details/135747952
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。