🛴 239.滑动窗口最大值
给你一个整数数组 nums，有一个大小为 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
| class Solution {
public:
//不是求滑动窗口中的和最大值，而是求每一个滑动窗口中的元素最大值
//暴力法是针对每一个窗口都从头筛选一遍
//保持对头始终是最大的元素
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
//判断极端情况
if(nums.size()<k||k==0)
return res;
//先累计一个滑动窗口，之后进一个出一个，每次都判断是不是最大
deque<int> windows;
int max=0;
int start=0;
//先累计一个窗口，保持对头元素最大
for(int i=0;i<k;++i){
while(!windows.empty()&&nums[i]>windows.back())
windows.pop_back();
windows.push_back(nums[i]);
}
//这是第一个窗口
res.push_back(windows.front());
//后面的元素也需要保持对头元素最大
for(int i=k;i<nums.size();++i){
//当前窗口元素已满，窗口的最大值元素只能在这里删除
if(windows.front()==nums[i-k])
windows.pop_front();
//保持对头元素最大,这里不能是等于，一旦当前窗口中出现两个相同的最大值
//前一个最大值就保不住了
//相当于windows的front保存的是最近几个窗口的最大值
while(!windows.empty()&&nums[i]>windows.back())
windows.pop_back();
windows.push_back(nums[i]);
res.push_back(windows.front());
}
return res;
}
};
|
这段代码将形成一个完整的窗口前和一个完整的窗口后，形成一个完整的窗口前，这样进一步区分元素入队的判断条件，减小判断时的消耗，如果不将形成窗口之前和之后分开，那么就需要在统计结果时和对头元素出对时进行进一步的判断
执行流程
- 不停地入队元素，保持队列的非递增，也就是对头元素始终是最大值
- 当当前元素与对头元素相同，相当于当前窗口元素已满，需要删除元素
- 当形成一个完整的窗口之后，就可以统计结果
- 返回最终的结果
代码
根据以上分析，得出以下代码：
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
| class Solution {
public:
//不是求滑动窗口中的和最大值，而是求每一个滑动窗口中的元素最大值
//暴力法是针对每一个窗口都从头筛选一遍
//保持对头始终是最大的元素
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
//判断极端情况
if(nums.size()<k||k==0)
return res;
//先累计一个滑动窗口，之后进一个出一个，每次都判断是不是最大
deque<int> windows;
//始终保持对头元素最大
for(int i=0;i<nums.size();++i){
//当前窗口元素已满，窗口的最大值元素只能在这里删除
if(i>=k&&windows.front()==nums[i-k])
windows.pop_front();
//保持对头元素最大,这里不能是等于，一旦当前窗口中出现两个相同的最大值
//前一个最大值就保不住了
//相当于windows的front保存的是最近几个窗口的最大值
while(!windows.empty()&&nums[i]>windows.back())
windows.pop_back();
windows.push_back(nums[i]);
if(i>=k-1)
res.push_back(windows.front());
}
return res;
}
};
|
总结
核心就是始终保持对头元素最大，只有当当前对头元素超出窗口范围才删除