题解 | #滑动窗口的最大值#

//抄的题解的。注意区分单调队列与优先队列。一个升序的单调队列会自动把比它小的全部出队掉，保证自己进队后还能维持有序性（不是进队时找个正确的位置插入，而是直接就在队尾进队，前面有比自己小的就全部出队滚蛋）。而优先队列则是用了大顶堆的思想，把最大值调整到堆顶（也就是队头）。
//如果只是要实现单调队列本身，使用deque就行。每个元素入队时不断查询队尾（查询队尾只有双端队列才能做到）的元素是否比自己大，比自己小的就出队（pop_back），然后再继续查询队尾，直到比自己大为止。
//本题的滑动窗口，不仅要维护队列中的一个最大值，还需要保证窗口的有效性，因此在前面已经离开了窗口左端的过期的值是需要被删除的。这就要求我们既在队尾出队，也在队头出队。
#include <deque>
#include <vector>
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        deque<int>d;//用来装下标
        vector<int>res;
        if(size<=0 || size>num.size())
            return res;
        
        for(int index=0;index<num.size();index++){
            int current=num.at(index);
            while (!d.empty() && num.at(d.back())<current) {//每进一个新的元素之前，都要从单调队列的末端向下遍历，把比新元素小的一个不留的驱逐出去。
                d.pop_back();
            }
            d.push_back(index);
            if(d.front()+size<=index) {//将双端队列左端的过期index也清除掉。一般一次最多只有一个会过期。
                d.pop_front();
            }
            if(index>=size-1)
            {//把单调队列中的最大值放进res
                res.push_back(num.at(d.front()));
            }
            
        }
        return res;

    }
};