Monotone Queue - 单调队列

https://blog.csdn.net/A_Bright_CH/article/details/77076228
使用单调队列就涉及到去头和删尾：

1、队列的头一定是在一段时间前就加入了队列，现在的队列头会不会离开了我们处理的区间呢？如果它离我们正在处理的i太远了，我们就要把它去掉，去除冗杂的信息。

2、为了保证队列的递减性，在从列队尾新插入元素v时，要考虑队列尾的值是否大于v，如果是，队列呈现 队列尾-1的值 > 队列尾的值 > v ，此时队列递减性没有消失；如果不是，队列呈现 队列尾-1的值 > 队列尾的值 < v ，队列递减性被打破。

为了维护递减性，我们做如下考虑：v是最新值，它的位置是目前最靠后的，它可成为以后的最大值，必须留下；队列尾-1的值与v大小不定，不能冒然删去它；队列尾的值夹在v和队列尾-1之间，它不但不是最大值，对于以后的情况又不如v优，因为v相比队列尾更靠后（v可以影响到后m个值，队列尾只能影响到从它的位置往后数m-1个值），而且值更大，所以删队列尾是必定的。



在维护好一个 区间正确、严格递减 的单调递减队列后，队列头就是当前区间的最大值了。

整理归纳单调队列的定义：

1、维护区间最值；
2、去除冗杂状态；
3、保持队列单调（最大值是单调递减序列，最小值是单调递增序列）；
4、最优选择在队首。



整理归纳单调队列的使用方法：

1、维护队首（对于上题就是如果你已经是当前的m个之前那你就可以被删了） ；
2、在队尾插入（每插入一个就要从队尾开始往前去除冗杂状态） ；
3、取出需要的最优解（队列头的值即是）；
4、借助最优解，得到目前所求的最优解（通常此处插入DP方程）。



单调队列的原理：

在处理f[i]时，去除冗杂、多余的状态，使得每个状态在队列中只会出现一次；同时维护一个能瞬间得出最优解的队列，减少重新访问的时间；在取得自己所需的值后，为后续的求解做好准备。

https://www.cnblogs.com/neverforget/archive/2011/10/13/ll.html

    单调队列，望文生义，就是指队列中的元素是单调的。如：{a1,a2,a3,a4……an}满足a1<=a2<=a3……<=an,a序列便是单调递增序列。同理递减队列也是存在的。

    单调队列的出现可以简化问题，队首元素便是最大（小）值，这样，选取最大（小）值的复杂度便为o（1），由于队列的性质，每个元素入队一次，出队一次，维护队列的复杂度均摊下来便是o（1）。

如何维护单调队列呢，以单调递增序列为例：

1、如果队列的长度一定，先判断队首元素是否在规定范围内，如果超范围则增长队首。

2、每次加入元素时和队尾比较，如果当前元素小于队尾且队列非空，则减小尾指针，队尾元素依次出队，直到满足队列的调性为止

要特别注意头指针和尾指针的应用。

单调队列的应用仍有很多实例，这一不能一一道出。

   首先考虑问题需要的时间复杂度如果是o（n）的算法，单调队列是首选。

   其次要善于观察分析，发现题目中的单调性。决策的单调（合并果子），要求问题的特性（window），元素价值和其在原序列中位置的单调（志愿者），问题结果的单调（广告印刷）。

https://www.cnblogs.com/ka200812/archive/2012/07/11/2585950.html

单调队列是一种严格单调的队列，可以单调递增，也可以单调递减。队首位置保存的是最优解，第二个位置保存的是次优解，ect。。。

单调队列可以有两个操作：

1、插入一个新的元素，该元素从队尾开始向队首进行搜索，找到合适的位置插入之，如果该位置原本有元素，则替换它。

2、在过程中从队首删除不符合当前要求的元素。

单调队列实现起来可简单，可复杂。简单的一个数组，一个head，一个tail指针就搞定。复杂的用双向链表实现。

用处：

1、保存最优解，次优解，ect。

2、利用单调队列对dp方程进行优化，可将O(n)复杂度降至O(1)。也就是说，将原本会超时的N维dp降优化至N-1维，以求通过。这也是我想记录的重点

是不是任何DP都可以利用单调队列进行优化呢？答案是否定的。

记住！只有形如 dp[i]=max/min (f[k]) + g[i]  （k<i && g[i]是与k无关的变量）才能用到单调队列进行优化。

优化的对象就是f[k]。

https://blog.csdn.net/zhjchengfeng5/article/details/7653120
单调队列很好理解，就是一个双向队列，队首队尾允许删除操作，队尾进行添加操作，维护整个队列的严格单调性，即队列中不存在相等的元素（这样时间常数小一点）。

那么用单调队列优化的DP应该具有怎样的性质呢？

假如我们有下面的DP转移方程：

    f[i] = min( f[j] ) + a[i]

那么当 j 满足一个条件： Low[i] <= j <= Up[i] ，这里的 Low 和 Up 是关于 i 的单调函数，而且是单调递增的，为什么呢？联系经典的单调队列入门题： Sliding Window 想想就清楚了： 当我用下一个 Low[i] 的时候，Low[i] 必须大于等于 Low[i-1] ，因为队首涉及到了要出队列的操作，而队尾的元素上界： Up 也是必须具有单调递增的性质，因为再用队尾的元素的时候，涉及到添加元素的操作。如果还是不很明白，那么联系 Sliding Window 仔细想想这个单调队列删除插入的过程即可。很好想通的。


https://oi.men.ci/monotone-queue-notes/

单调队列，就是单调的队列，通常用来解决滑动窗口的最值问题，可以应用到 DP 的优化上。一个单调队列中的元素总是单调递增（或递减）的。

滑动窗口

例：有一个队列，每次从队尾加入一个元素，或从队首删除一个元素，并在任何时刻求整个队列的最大值。

一个很直接的想法是使用优先队列 priority_queue 即堆，堆可以在 $O(1)$ 的时间内求出最大值，但每次加入或删除时需要 $O({\log}n)$ 的时间完成堆的调整，但是用了堆后就不能按照进队的顺序出队了！这时候你可以大胆地写一个平衡树或者 set——如果你不怕多出来的 $\log$ 和平衡树常数带来的 TLE 的话。

单调队列就是解决这类问题的数据结构，我们用一个辅助队列，使该队列的首元素总是原队列的最大值，这样就可以 $O(1)$ 地求出队列的最大值了。

维护单调队列

现有需要维护最大值的队列 Q，和辅助队列 M，设计算法使任何时刻时 M 队首元素都是当前 Q 的最大值。

每次在 Q 的队尾加入元素 x 时，也将其加入到 M 中，从 M 的队尾向前遍历，将遍历到的所有 小于等 x 的元素全部删除，因为它们在 x 之前被加入到队列中，在 x 出队前它们就已经都出队了，即在 x 出队前这些元素不可能成为队列中的最大值。

每次在 Q 的队首删除元素时，将要删除的元素与 M 的队首元素比较，如果该元素与 M队首元素相等，即该元素为执行删除操作前队列的最大值，则同时也要将 M 的队首元素删除，使原 Q 的次小值成为 M 的队首元素，保证 M 的队首元素是删除操作后 Q 中最大的元素。

应用

状态转移方程形如 $f[x]=\max\{g(k)\}+w[x]$ 的动态规划可以使用单调队列来优化。

实现

因为同时要从队列的两端添加、删除，所以要使用 deque 实现，而不是 queue。

template <typename T>
struct MonotoneQueue {
    std::deque<T> q, m;

    void push(const T &x) {
        q.push_back(x);
        while (!m.empty() && m.back() < x) m.pop_back();
        m.push_back(x);
    }

    void pop() {
        T x = q.front();
        q.pop_front();
        if (x == m.front()) m.pop_front();
    }

    size_t size() {
        return q.size();
    }

    T top() {
        return m.front();
    }
};