题目
239. 滑动窗口最大值 - 力扣（LeetCode）
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 示例 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
2
3
| 1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
|
思路一
说明
我最初自己想的思路是，用一个队列来维护滑动窗口，并用一个当前最大值来记录滑动窗口内的最大值。每次滑动窗口满了（为k），都将这个最大值写入返回值数组中。
当滑动窗口左侧缩限的时候，判断被出队列的是否为最大值
- 不是最大值，不用更新当前最大值；
- 是最大值，从队列剩余数据中选出一个新的当前最大值；
这样就能维护出一个题目需要的数组。代码如下
代码
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int curMax = INT32_MIN;
vector<int> retV;
int size = 0;
queue<int> que;
for(auto&e:nums)
{
if(size == k)
{
int popNum = que.front();
que.pop();
size--;
if(popNum == curMax)
{
int count = size;
curMax = que.front();
while(count --)
{
int temp = que.front();
curMax = max(curMax,temp);
que.pop();
que.push(temp);
}
}
}
if(size < k)
{
curMax = max(curMax,e);
que.push(e);
size++;
}
if(size == k)
{
retV.push_back(curMax);
}
}
if(nums.size() < k)
{
retV.push_back(curMax);
}
return retV;
}
};
|
这个代码的时间复杂度是O(N*K)，因为最差情况视作每次都需要重新遍历队列，时间复杂度就很高了。但思路应该是没有问题的，通过了大部分测试用例，只不过在大测试用例中超时了，因为此时K很大，如果需要重新遍历对列找出第二个最大值，耗时会很高。
当然，我想出了另外一个优化方案，就是对于这种大k的情况，维护一个队列中第二大的数据，就不需要遍历对列了。但这样很麻烦，且这个思路本身就已经不适合解这道题了，于是没有尝试。
思路二
说明
思路二是代码随想录上面的，使用一个单调递增/递减对列来维护这个最大值。对于本题而言，使用单调递减序列更适合。
这个对列需要实现push/pop/front三个功能，其中front就是当前滑动窗口中的最大值：
- push：当当前值小于对列尾部值时，直接插入；大于时，出队列尾部数值，直到当前值小于队列尾部数值，插入；
- pop：如果滑动窗口删除的数据和队头数据一致，出队头数据（因为这是一个需要被删除的最大值）；不一致则不做任何操作；
- front：获取队头数据；
注意，这个单调对列只是针对本体的需求来写的。本体只是需要滑动窗口中的最大值，对于对列而言并不需要维护滑动窗口中的所有元素，只需要维护几个递减的最大值就行了。
本题也不能用堆来实现，因为堆只能删除堆顶元素，堆顶元素不一定是滑动窗口需要移除的元素。这会导致堆内元素和当前滑动窗口内的元素不对应，会出现问题。
使用C++的deque数据结构就可以实现一个这样的对列。deque是stack/queue默认的底层容器，stack/queue在C++中是容器适配器（因为它们并不是直接实现的，而是借助其他容器实现的）。deque的特性让它支持队头队尾的插入删除操作。
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
|
class MyQueue
{
deque<int> que;
public:
void pop(int value)
{
if (!que.empty() && value == que.front())
{
que.pop_front();
}
}
void push(int value)
{
while (!que.empty() && value > que.back())
{
que.pop_back();
}
que.push_back(value);
}
int front()
{
return que.front();
}
};
|
代码
有了这个单调递减的对列后，我们现在只需要将vector中的元素按K滑动窗口大小往对列输入就可以了。注意，删除元素的时候要删除当前滑动窗口第一个元素，再加入新元素。
第一次遍历后需要插入一次最大值是因为第二个循环可能不会进去，而且第二个循环中会先移动窗口再插入新的最大值，如果不提前插入第一个最大值，可能会漏掉。
另外，本体限定K不会大于数组的长度，所以第一个循环用K做边界是不会数组越界的。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| class Solution {
class MyQueue
{
deque<int> que;
public:
void pop(int value)
{
if (!que.empty() && value == que.front())
{
que.pop_front();
}
}
void push(int value)
{
while (!que.empty() && value > que.back())
{
que.pop_back();
}
que.push_back(value);
}
int front()
{
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> retV;
for(int i =0;i<k;i++)
{
que.push(nums[i]);
}
retV.push_back(que.front());
for(int i = k;i<nums.size();i++)
{
que.pop(nums[i - k]);
que.push(nums[i]);
retV.push_back(que.front());
}
return retV;
}
};
|
The end
单调递增/单调递减的对列思想还是第一次遇到，学到了。
爱发电
