滑动窗口的最大值（每次滑动减少窗口内元素比较次数）

/*
暴力O(n*k) 每一个数字都从k个窗口中判断你最大值
单调队列 O(n) 
遍历数组中每一个元素 用一个容器来存放每次遍历的值
如果当前元素比容器最后一个元素大，容器最后一个元素删除,然后继续当前元素和最后一个比较。为了保证队列中最大值始终位于队头
如果容器头部元素已经不在容器范围内自然出队
当前元素入队
当滑动窗口的首地址大于等于窗口大小时，每入队一次将最大值（队头元素）存放在res向量中。
*/
class Solution {
public:
    vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
        vector<int> res;
        deque<int> s;
        if(size <= 0)return res;
        for(int i = 0; i < num.size(); i++){
            // 从后面依次弹出队列中比当前num值小的元素，比num小的值对结果没有影响
            // 同时保证队列首元素为当前窗口最大值下标
            while(s.size() && num[s.back()] <= num[i]) s.pop_back();

            //队首元素元素不在窗口中，需要弹出 用下标判断
            while(s.size() && i - s.front() + 1 > size) s.pop_front();

            s.push_back(i); //把每次滑动的num下标加入队列

            //当滑动窗口首地址i大于等于size时才开始写入窗口最大值 size要大于0
            if( size && i+1 >= size) res.push_back(num[s.front()]);
        }
        return res;
    }
};