单调队列
之前听松爷扯过单调队列，于是学了一番，感受是这样的： 单调队列大法好， O ( n log n ) O ( n log n ) 变 O ( n ) O ( n ) ！ 性质 单调队列，顾名思义，是一个“单调”的队列。 如何便是单调？单调递增/递减。 假设下面说的都是单调递减队列。 插入元素时，如何维护单调队列的单调性？ 这是单调队列中最基础的问题。 解决方法往往很粗暴： 先把队尾所有小于插入元素的都删除 ，然后插入元素。 这样就有序了。但是有个问题，为什么可以直接删除那些元素？ 与要维护的东西的性质有关。 显然，我是懒得手打循环队列的。上STL大法—— 双端队列 。 #include <deque> using namespace std ; int main () { deque < int > q ; q . push_front ( 1 ); //队首插入1 printf ( "%d \n " , q [ 0 ]); //滋磁随机访问！ q . push_back ( 2 ); //队尾插入2 q . push_back ( 3 ); //队尾插入3 q . pop_back (); //弹出队尾元素 } 例题：滑动窗口 一个长度为 n n 的序列，有一个长度为 k k 窗口在其中滑动。 求出：每一个位置，窗口中元素的 最大值、最小值 。 Example: 窗口位置 最小值 最大值 [ 1 3 - 1 ] - 3 5 3 6 7 - 1 3 1 [ 3 - 1 - 3 ] 5 3 6 7 - 3 3 1 3 [ - 1 - 3 5 ] 3 6 7 - 3 5 1 3 - 1 [ - 3 5 3 ] 6 7 - 3 5 1 3 - 1 -...