滑动窗口的最大值

思路：

用单调队列维护窗口中的元素的单调性

1.将序列中的每个元素都插入单调队列中，将小于需要插入的这个节点的数从队尾弹出

2.再将这个节点插入单调队列中

3.将超出窗口范围的队首节点从队首弹出队列

4.输出每个窗口中的第一个值就是这个窗口的最大值

单调队列的性质：

1.队首的元素永远是队列中最大或最小的元素，可以输出队首元素，不一定需要将队首元素弹出

2.只能从队尾插入元素，可以从队首和队尾弹出元素，单调队列实际是双端队列的一个典型应用，只是相比双端队列，单调队列只能从队尾插入，双端队列可以从队尾和队首插入元素

3.在队尾插入元素的时候，将大于或（小于）当前的元素弹出后再把当前元素插入到队列中

代码：

class Solution {
public:
    //定义一个函数用于求窗口的最大值，传入需要求的序列，和窗口的长度，返回的是每个窗口的最大值数组
    vector<int> maxInWindows(vector<int>& num, int size) {
        //定义一个res容器用于求每个窗口的最大值的数组
       vector<int>res;
       //如果需要求的序列的长度为0或者窗口的长度为0，或者序列的长度比窗口的长度还短，就表示不存在窗口的最大值
       if(num.size()==0||size==0||num.size()<size){
        return res;
       }
       //定义一个单调队列维护窗口内的区间的单调性（降序）：即窗口的第一个元素是窗口中的最大值
       deque<int> p;
       //遍历整个序列，将每个数插入单调队列中：
       //1.只要队列不为空，就将小于这个数的数出队列（从队尾出去）
       //2.再将该元素插入到单调对列中
       //3.再判断一下队首元素是否超出窗口的范围，如果超出窗口的范围，就让队首出队（从队头出去）
       //因为对于单调队列是双端队列，所以是可以从队头或队尾出队列的，但是单调队列不同点在于只能在队尾插入元素
       //4.将达到窗口长度时，就将这个窗口的第一个元素输出就是这个窗口的最大元素
       for(int i=0;i<num.size();i++){
           while(!p.empty()&&num[p.back()]<num[i]){
            p.pop_back();
           }
           p.push_back(i);
           if(p.front()+size<=i){
                p.pop_front();
           }
           if(i+1>=size){
             res.push_back(num[p.front()]);
           }
          
       }


       return res;
    }
};