All About Programming: POJ 2823 Sliding Window - 浙西贫农

单调队列，顾名思义，就是一个元素单调的队列，那么就能保证队首的元素是最小（最大）的，从而满足动态规划的最优性问题的需求。

单调队列，又名双端队列。双端队列，就是说它不同于一般的队列只能在队首删除、队尾插入，它能够在队首、队尾同时进行删除。

【单调队列的性质】

一般，在动态规划的过程中，单调队列中每个元素一般存储的是两个值：

1. 在原数列中的位置（下标）

2. 他在动态规划中的状态值

而单调队列则保证这两个值同时单调。

从以上看，单调队列的元素最好用一个类来放，不这样的话，就要开两个数组。。。

插入方法（以最大单调队列为例）：

在插入一个元素前，先判断队列是否为空（head<=tail），然后再判断队尾元素是否比要插入的元素小（q[tail].val<data[insert]），如果是的话，则将队尾元素删除（--tail）。

重复以上过程，直至为空或队尾元素比其大。

删除方法：

这个要根据具体题目而定。在本题是如果当前的INDEX与队首的INDEX相差大于等于K，则删除。

Labels