最怕是春归了秣陵树
人老了偏在建康城
C++，双端队列。
其实看到这道题，一开始想到的就是用最大堆和哈希，窗口每次移动的时候，堆顶元素都是最大值。然后通过哈希判断堆顶元素是否还在窗口内，不在窗口内则弹出堆顶。这样做的复杂度是O(nlogn)。
过了后觉得不踏实，还是去搜了别人的解法，最终看到了一个词，双端队列。
双端队列就是可以从队尾队首弹出和压入元素，区别于普通队列，和双向链表类似。
这里可以用双端队列达到之前最大堆的作用，即队首始终记录窗口内的最大值，怎么做到呢？
类似于之前维护堆顶的规则，窗口每移动一次，对于新元素X，如果大于队尾，则将队尾移除，直至队列只有大于等于X的元素为止，这样可以保持队首永远是最大值。同时窗口每移动一次，都需要将队首的最大值记录作为答案，还需要注意的是，队首元素可能已经不在窗口内，所以每次还得判断最大值在不在窗口内，为了更加简便，双端队列存储的应该是元素的索引而不是值。
代码如下：
class Solution {
public:
vector<int> maxInWindows(const vector<int> &num, unsigned int size) {
vector<int> ans;
deque<int> q;
if (num.empty() || size <= 0 || size > num.size()) return ans;
for (int i = 0; i < size && i < num.size(); i++) {
while (!q.empty() && num[i] > num[q.back()])
q.pop_back();
q.push_back(i);
}
ans.push_back(num[q.front()]);
for (int i = size; i < num.size(); i++) {
if (i - q.front() >= size)
q.pop_front();
while (!q.empty() && num[i] > num[q.back()])
q.pop_back();
q.push_back(i);
ans.push_back(num[q.front()]);
}
return ans;
}
};
