晚上因为看老罗发布会，脑袋有些短路，所以这道题的思路是看了书以后才理解的。
大致思路是借助一个辅助的队列（需要时双端队列）来存储当窗口移动到前元素时的最大值。在添加的时候，当窗口移动到某个值得时候，如果辅助队列中的最大值小于当前值，就之前小于它的都删掉，因为这些值以后就没用了，但是不论如何都要保留当前值，因为可能前面的最大值随着窗口移出的时候最大值元素也随之移出，次小的元素可能会被作为新的最大值。
因为要再窗口移动时候把属于移出元素的最大值给弹出，所以再 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;
}
};
|