这是一道滑窗+单调队列的题目
单调队列是怎样的
不懂单调队列的看一下这一段：
单调队列真是一种让人感到五味杂陈的数据结构，它的维护过程更是如此…..就拿此题来说，队头最大，往队尾方向单调……有机会站在队头的老大永远心狠手辣，当它从队尾杀进去的时候，如果它发现这里面没一个够自己打的，它会毫无人性地屠城，把原先队里的人头全部丢出去，转身建立起自己的政权，野心勃勃地准备开创一个新的王朝…..这时候，它的人格竟发生了一百八十度大反转，它变成了一位胸怀宽广的慈父！它热情地请那些新来的“小个子”们入住自己的王国……然而，这些小个子似乎天性都是一样的——嫉妒心强，倘若见到比自己还小的居然更早入住王国，它们会心狠手辣地找一个夜晚把它们通通干掉，好让自己享受更大的“蛋糕”；当然，遇到比自己强大的，它们也没辙，乖乖夹起尾巴做人。像这样的暗杀事件每天都在上演，虽然王国里日益笼罩上白色恐怖，但是好在没有后来者强大到足以干翻国王，江山还算能稳住。直到有一天，闯进来了一位真正厉害的角色，就像当年打江山的国王一样，手段狠辣，野心膨胀，于是又是大屠城……历史总是轮回的。
（虫子的世界的评论）
本题思路
用队列（我是用数组模拟的）存储窗口内元素的索引和值，队列头部维护当前窗口最大值。遍历一遍数组。如果有超出窗口范围的元素，先将他移除。然后从队列尾部移除小于当前元素的无效值，移除完后将当前元素加入队列。最后如果窗口已经形成，记录队列头部最大值。
时间复杂度O(n)，空间复杂度O(n)。
代码
int b[100010][2],s=1,w=0;
vector<int> c;
vector<int> maxSlidingWindow(vector<int>& a,int k) {
for(int i=0;i<=a.size()-1;i++) {
if(b[s][0]<=i-k) {
s++;
}
while(w>=s&&b[w][1]<a[i]) {
w–;
}
w++;
b[w][1]=a[i];
b[w][0]=i;
if(i>=k-1) {
c.push_back(b[s][1]);
}
}
return c;
}
};
