CodingInterview-滑动窗口的最大值

晚上因为看老罗发布会,脑袋有些短路,所以这道题的思路是看了书以后才理解的。

大致思路是借助一个辅助的队列(需要时双端队列)来存储当窗口移动到前元素时的最大值。在添加的时候,当窗口移动到某个值得时候,如果辅助队列中的最大值小于当前值,就之前小于它的都删掉,因为这些值以后就没用了,但是不论如何都要保留当前值,因为可能前面的最大值随着窗口移出的时候最大值元素也随之移出,次小的元素可能会被作为新的最大值。

因为要再窗口移动时候把属于移出元素的最大值给弹出,所以再 deque 里不能存放最大值,而应该存放最大值对应的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> maxInWindows;
if(num.size()==0 || size>num.size() || size<=0) return maxInWindows;
deque<int> maxNums;
for(int i=0;i<size;i++){
while(!maxNums.empty() && num[maxNums.back()]<=num[i]) maxNums.pop_back();
maxNums.push_back(i);
}
for(int i=size;i<num.size();i++){
maxInWindows.push_back(num[maxNums.front()]);
while(!maxNums.empty() && num[maxNums.back()]<=num[i]) maxNums.pop_back();
if(!maxNums.empty() && maxNums.front()<=(i-size)) maxNums.pop_front();
maxNums.push_back(i);
}
maxInWindows.push_back(num[maxNums.front()]);
return maxInWindows;
}
};