滑动窗口的最大值

思路:

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

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;
    }
};