1.解题思路

窗口滑动前，已经找到其中最大值，那么滑动以后新增的一个元素只需和之前找到的最大值比较，但是有一个问题，如果之前的最大值正好离开了窗口就会出现错误，因此需要一个可以各时刻最大值的数据结构。该数据结构要满足以下功能：

1）随窗口向后移动，会有一个元素离开窗口，如果离开的元素是之前的最大值，那么该数据结构要及时移除那个值；

2）随窗口向后移动，会有一个元素进入窗口，如果进入的元素比之前的元素小，但是前面的元素离开窗口时，该元素可能成为最大值，因此需要保留；如果进入元素比之前的元素大，那么之前较小的元素绝不可能成为之后任意时刻的最大值了，无需保留，因此该数据结构里的元素满足递减的数学关系。

该数据结构需要在尾部删除和增加元素，需要在头部删除元素，因此双端队列deque最合适。

2.代码

#include <deque>
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        deque<int> que;  //记录滑动窗口移动后除增加元素外的最大值的下标的双端队列
        vector<int> res; //返回结果
	   
	  //窗口尺寸大于数组尺寸或为0，直接返回
        if(num.size()<size || size==0) 
            return res;
       
	  for(int i=0;i<num.size();++i){
         	//当新元素进入窗口时，如果队列中有值，新元素从后向前依次比较，如果新元素更大，因为它的位置更靠后，前面小于它的值不可能会是当前窗口最大值了，因此删除
            while(!que.empty() && num[que.back()]<=num[i])
                que.pop_back();
        	//新元素不论大还是小都要入队
            que.push_back(i);
			//窗口移动使前面的元素过期后要及时清除
            if(que.front()+size==i)
                que.pop_front();
			//返回当前窗口的最大值，因为队列动态更新，保证了其中的元素都没过期，且其中元素满足递减关系，队首元素即当前窗口最大值
            if(i+1>=size)
            res.push_back(num[que.front()]);
        }
        return  res;
    }
        
};