滑动窗口的最大值

scorlw 发布于

滑动窗口的最大值

关键词:滑动窗口最值、deque

题目描述

给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。

示例 1:

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

解法

解法一:

思路:

  • 这种滑动窗口的最值问题,一般可以考虑使用队列或者栈来对最值进行保存。
  • 当新加入的值比队列末尾的值大时,则pop掉队列尾部的值,一直到可以保证新队列是递减的(可能包含相等的值)。

算法流程:

  1. 判断nums 的size以及k值等,增强函数的鲁棒性;
  2. 建立队列,用来保存最值;
  3. 首先根据第一个窗口的值来初始化队列;
  4. 之后根据窗口的移动,判断是否pop当前的队首值以及保证队列的递减性。

代码:

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 Solution {
public:
deque<int> dq;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
if(n <= 0) return {};
vector<int> res;

for(int i = 0;i<k;i++){
//单调减
while(dq.size() && nums[i] > dq.back()) dq.pop_back();//当队列中有元素时,pop_back出所有比nums[i]小的数
dq.push_back(nums[i]);
}
res.push_back(dq.front());
for(int i = k;i<n;i++){

//先删除nums[i-k]之后添加nums[i],若是先添加则会破坏dq的原有结构,造成错误

//若是窗口划过的元素nums[i-k]刚好为dq的首节点,即最大值时 将dq头删去
if(dq.front()==nums[i-k])
dq.pop_front();
//维护单调性
while(dq.size()&&nums[i]>dq.back()) dq.pop_back();
//个数不能大于k,我感觉不加也可以
if(dq.size()==k) dq.pop_back();
dq.push_back(nums[i]);
res.push_back(dq.front());
}
return res;
}
};

带有IO的代码:

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
#include <iostream>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(vector<int>& nums, int k)
{
vector<int> res;
if(k > nums.size() || nums.size() <= 0 || k <= 0) return res;
deque<int> dq;
dq.push_back(nums[0]);
for(int i = 1; i < k; i++){
while(dq.size() && nums[i] > dq.back()) dq.pop_back();
dq.push_back(nums[i]);
}
res.push_back(dq.front());
for(int i = k; i < nums.size(); i++){
if(dq.front() == nums[i-k])
dq.pop_front();
while (dq.size() && nums[i] > dq.back()) dq.pop_back();
dq.push_back(nums[i]);
res.push_back(dq.front());
}
return res;
}

int main()
{
vector<int> nums;
{//对于输入的代码,可以使用大括号括起来,输入结束后直接释放局部变量
int a;
while(cin >> a){
nums.push_back(a);
if(cin.get() == '\n') break;//注意位置,需要放在后面,否则读不到最后一个数据
}
for(int i : nums){
cout << i << " ";
}
cout << endl;
}
int k;
cin >> k;
for(int a : maxSlidingWindow(nums, k))
{
cout << a << " ";
}
cout << endl;

system("pause");
return 0;
}

知识点

  1. 队列deque