题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
思路
考虑利用一个单调的双端队列（deque）实现对区间最大值的维护。这个deque的前端就是这个区间的最大值，而其后续的部分则是接下来的窗口中有可能取到的最大值。
再考虑一个双指针，中间的部分即为窗口。我们只需要考虑left和right的元素即可。
例如：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
1
2
3
4
5
6
7
8
| 滑动窗口的位置 最大值 deque
--------------- ----- --------
[1 3 -1] -3 5 3 6 7 3 3, -1
1 [3 -1 -3] 5 3 6 7 3 3, -1, -3
1 3 [-1 -3 5] 3 6 7 5 5
1 3 -1 [-3 5 3] 6 7 5 5, 3
1 3 -1 -3 [5 3 6] 7 6 6
1 3 -1 -3 5 [3 6 7] 7 7
|
对于最开始的3个，最大值是3，然而在窗口向右移动时，若3弹出，-1有可能成为某个区间的最大值，因此在deque中保留了-1.
当5进入，它比deque中任何一个元素都大（只要它比deque front大），所以deque全部pop，并加入5.
如果进入的某个元素不大于deque front，却大于deque back，那么deque中比这个元素小的数在今后的区间内就不会成为最大值了，因此将其全部pop。
然而在实现的过程中，最令我困惑的是，窗口左端何时出，右端何时入。
声明需要的变量。
1
2
3
4
5
| deque<int> q;
vector<int> res;
int left = 0;
int right = 0;
int len = nums.size();
|
首先解决前k个的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| while(right < k){
if(nums[right] > q.front()){
while(!q.empty()){
q.pop_back();
}
q.push_front(nums[right]);
}else{
while(!q.empty() && nums[right] > q.back()){
q.pop_back();
}
q.push_back(nums[right]);
}
right++;
}
res.push_back(q.front());
|
再看其余的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| while(right < len){
if(nums[left] == q.front()){
q.pop_front();
}
if(nums[right] > q.front()){
while(!q.empty()){
q.pop_front();
}
q.push_front(nums[right]);
}else
if(nums[right] <= q.front()){
while(!q.empty() && q.back() < nums[right]){
q.pop_back();
}
q.push_back(nums[right]);
}
right++;
left++;
res.push_back(q.front());
}
|
事实上，我们需要使此后的区间长度为k+1，因为需要判断front是否需要弹出。
完整代码
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
| class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q;
vector<int> res;
int left = 0;
int right = 0;
int len = nums.size();
while(right < k){
if(nums[right] > q.front()){
while(!q.empty()){
q.pop_back();
}
q.push_front(nums[right]);
}else{
while(!q.empty() && nums[right] > q.back()){
q.pop_back();
}
q.push_back(nums[right]);
}
right++;
}
res.push_back(q.front());
while(right < len){
if(nums[left] == q.front()){
q.pop_front();
}
if(nums[right] > q.front()){
while(!q.empty()){
q.pop_front();
}
q.push_front(nums[right]);
}else
if(nums[right] <= q.front()){
while(!q.empty() && q.back() < nums[right]){
q.pop_back();
}
q.push_back(nums[right]);
}
right++;
left++;
res.push_back(q.front());
}
return res;
}
};
|
