使用双端队列保存进入窗口数字的下标,如果双端队列为空,那么插入;
如果队列的最后的下标所对应的数要大于当前的数,那么从后面插入当前的数,应为这个数可能是以后的最大值;
如果队列的最后的下标所对应的数要小于当前的数,那么将所有要小于当前数的元素都弹出去;
最后保证所有不在窗口内的数出队列;
队列最前面的数即为当时窗口的最大值。

这里存储元素的下标是一个很巧妙的方法。因为如果只存储元素大小的话,不知道队列里元素是否已经不在窗口之内。

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:
/**
* @param nums: A list of integers.
* @return: The maximum number inside the window at each moving.
*/
vector<int> maxSlidingWindow(vector<int> &nums, int k) {
vector<int> result;
if (nums.size() < k) return result;
deque<int> window;
for (int i = 0; i < nums.size(); i++) {
while (!window.empty()) {
int back = nums[window.back()];
if (back <= nums[i])
window.pop_back();
else
break;
}
window.push_back(i);
if (i - window.front() >= k)
window.pop_front();
if (i + 1 >= k)
result.push_back(nums[window.front()]);
}
return result;
}
};