滑动窗口最值

暴力方法：遍历的过程中每次遍历一遍窗口找到最大的数值，这样很明显是O(n × k)的算法。

问题就是有没必要遍历一遍窗口来找到最大值。

直观的会想用一个大根堆（优先级队列）来存放这个窗口里的k个数字，这样就可以知道最大值是多少了， 但是问题是这个窗口是移动的，而大根堆每次只能弹出最大值，我们无法移除其他数值，所以不能用大顶堆。

这时候单调队列呼之欲出：

其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

只维护可能成为窗口最大值的元素是什么意思？

现代官场更加能阐明这个基本道理。

比如你这个倒霉蛋25岁二本毕业在机关当科员， 熬了十年后老处长退休， 你们科长升处长， 你升科长。你梦想着再熬10年处长退休然后你接班。结果是赵家人不讲武德。直接空降一个25岁的付处。他比你先接班，你等他退休也没戏， 所以这一辈子和处长没关系，自然可以从queue里pop out， 不用排队。排了也是白排。

也就是比你年轻的（在你之后被弹出），还比你厉害（比你值大），你就可以不用玩了。

比你年轻，但是没有你厉害，自然你还可以留着。

每个窗口最大值即为最前面的 front

动画演示如下：

代码

#include <vector>
class Solution {
public:
    deque<int> q;
    vector<int> res;
    // 包含两个操作：①添加新元素 ②弹出前面比新加入元素小的值
    void my_push(int val)
    {
        while( q.size() && val>q.back() ) q.pop_back();
        q.push_back(val);
    }
    // 弹出“寿终正寝”的元素
    void my_pop(int val)
    {
        // val==q.front()是什么意思？因为可能提前弹出元素，导致q.front()对不上
        if( q.size() && val==q.front() ) q.pop_front();
    }
    vector<int> maxInWindows(vector<int>& num, int size) {
        // 特判
        if( size==0 || size>num.size() ) return res;

        // 前k个单独处理
        for( int i=0; i<size; i++ ) my_push(num[i]);
        res.push_back(q.front());

        for( int i=size; i<num.size(); i++ ) 
        {
            // i-size 是滑动窗口的第一个值,也是可能被弹出的值
            my_pop(num[i-size]);
            my_push(num[i]);
            res.push_back(q.front());
        }
    return res;
    }
};