Leetcode239. 滑动窗口最大值

题目描述

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：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：

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

示例 3：

1
2
输入：nums = [1,-1], k = 1
输出：[1,-1]

示例 4：

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

示例 5：

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

提示：

  • 1≤nums.length≤1051 \leq nums.length \leq 10^5
  • −104≤nums[i]≤104-10^4 \leq nums[i] \leq 10^4
  • 1≤k≤nums.length1 \leq k \leq nums.length

解题思路

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

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

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

**Warning：**在扔掉队列中元素的时候必须判断队列是否为空，防止出现段错误！！！

示例代码如下：

示例代码

方法一：暴力法

1
2
3
4
5
6
7
8
9
10
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×n)O(k \times n)

空间复杂度为：O(1)O(1)

方法二：双端队列法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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;
}