Monotonic queue

单调队列

“如果一个选手比你小还比你强，你就可以退役了。”——单调队列的原理

单调队列是一种主要用于解决滑动窗口类问题的数据结构，即，在长度为n的序列中，求每个长度k的区间的区间最值。它的时间复杂度是O(n)。

单调队列的基本思想是，维护一个双向队列（deque），遍历序列，仅当一个元素可能成为某个区间最值时才保留它。

形象地打个比方，上面的序列可以看成学校里各个年级XCPC选手，数字越大代表能力越强。每个选手只能在大学四年间参赛，毕业了就没有机会了。那么，每一年的王牌选手都在哪个年级呢？

一开始的时候，大三大四的学长都比较菜，大二的最强，而大一的等大二的毕业后还有机会上位，所以队列里有两个数。

一年过去了，原本大一的成为大二，却发现新进校的新生非常强，自己再也没有机会成为最大值了，所以弹出队列。

又过了一年，新入校的新生尽管能力只有1，但理论上只要后面的人比他还菜，还是可能成为区间最大值的，所以入队。

终于，原本的王牌毕业了，后面的人以为熬出头了，谁知道这时一个巨佬级别的新生进入了集训队，这下其他所有人都没机会了。

总之，观察就会发现，我们维护的这个队列总是单调递减的。如果维护区间最小值，那么维护的队列就是单调递增的。这就是为什么叫单调队列。

例题 滑动窗口最大值

class Solution {
private:
    class MyQueue{
        public:
            deque<int> qu;
            void pop(int value) {
                if(!qu.empty() && value == qu.front()){
                    qu.pop_front();
                }
            }
            void push(int value){
                while(!qu.empty() && qu.back() < value) qu.pop_back();
                qu.push_back(value);
            }
            int front(){
                return qu.front();
            }
    };
public:

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector<int> result;
        for(int i = 0; i < k; i++) {
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for(int i = k; i < nums.size(); i++) {
            que.pop(nums[i - k]); // 滑动窗⼝移除最前⾯元素
            que.push(nums[i]); // 滑动窗⼝前加⼊最后⾯的元素
            result.push_back(que.front()); // 记录对应的最⼤值
        }
        return result;
    }
};