Leetcode239. 滑动窗口最大值

2021年5月12日 572点热度 1人点赞 0条评论

题目描述

给你一个整数数组 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]

示例 3:

输入:nums = [1,-1], k = 1
输出:[1,-1]

示例 4:

输入:nums = [9,11], k = 2
输出:[11]

示例 5:

输入:nums = [4,-2], k = 2
输出:[4]

提示:

  • $1 \leq nums.length \leq 10^5$
  • $-10^4 \leq nums[i] \leq 10^4$
  • $1 \leq k \leq nums.length$

解题思路

这道题最简单的办法就是把每个窗口的最大值找出来并保存,毫无疑问,暴力法时间超出限制。

必须想办法使用一个更高效的算法。可以使用deque容器(记为window)来存储下标,进行如下的操作:

  1. window的最前端就是一个窗口的最大值的下标,这样就可以通过调用window.front()来用常数时间得到一个窗口的最大值;
  2. 当遇到新的数的时候,将新的数和window的末尾比较,如果末尾比新数小,则把末尾的数的下标扔掉,直到该队列的末尾比新数大或者队列为空的时候才停止。这样就可以保证队列里面的下标对应的元素是从大到小排列的;
  3. 需要保证队列中存储的下标在窗口内。由于新的数只有一个,只需要判断队列的最前端是否在窗口内就可以了。

Warning:在扔掉队列中元素的时候必须判断队列是否为空,防止出现段错误!!!

示例代码如下:

示例代码

方法一:暴力法

vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
    vector<int>ans;
    for(int i=0;i<nums.size()-k+1;++i)
    {
        int tempMax=*max_element(nums.begin()+i,nums.begin()+i+k);
        ans.push_back(tempMax);
    }
    return ans;
}

时间复杂度为:$O(k \times n)$

空间复杂度为:$O(1)$

方法二:双端队列法

vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
    if(k<2) return nums;
    deque<int>window;
    vector<int>ans;
    //处理第一个窗口的情况
    for(int i=0;i<k;++i)
    {
        //比较新的数和window的末尾
        while(!window.empty()&&nums[window.back()]<nums[i])
        {
            window.pop_back();
        }
        //末尾加入新数
        window.push_back(i);
    }
    //保存窗口的最大值
    ans.push_back(nums[window.front()]);

    for(int i=k;i<nums.size();++i)
    {
        //保证队列中存储的下标必须在窗口内
        if(!window.empty()&&window.front()<i-k+1||window.front()>i)
        {
            window.pop_front();
        }
        //比较新的数和window的末尾
        while(!window.empty()&&nums[window.back()]<nums[i]) 
        {
            window.pop_back();
        }
        //末尾加入新数
        window.push_back(i);
        ////保存窗口的最大值
        ans.push_back(nums[window.front()]);
    }
    return ans;
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论

您需要 登录 之后才可以评论