单调队列的定义是，队列中元素按照值的大小，按需排列。
例如队首为最大值，队尾为最小值。
在入队新元素时，从队尾入队，
为了保持单调性，删除队尾小于新元素的旧元素。

这样的操作能够保证，队列的队首为满足条件的最大值。
所谓条件一般都是指滑动窗口的长度，也就是说当窗口长度超过限制时出队。
这样，就能得到，距离当前元素位置l长度范围内的最大值。

在入队时，可能会删除一些元素，而这些删除元素相比新入队元素有两条特点：
1.距离当前位置更远，会更早因为滑动窗口长度限制而被删除。
2.值会相比当前元素小，在当前元素存在时，不可能会被选择为窗口内最值。
因此，这些被删除元素对所求的窗口内最值毫无影响。

两条特点体现了两个思想：1.喜新厌旧；2.优胜劣汰。
突然联想到互联网35岁淘汰的讨论，也体现了单调队列的思想。
35岁的年龄限制，生动形象地体现了窗口的滑动和窗口的长度限制。
年纪大且能力不如新青年的直接从队尾中被淘汰。
真是残忍。

这次是在熟悉多重背包问题时，碰到了利用单调队列的优化问题。

多重背包：有N种物品，物品i的体积、价值和数量分别为vi,wi,si，要装进一个体积为V的背包种，求最大价值。

朴素的做法是，将物品i进行si次01背包操作，较为暴力的使用01背包模型来解决。

朴素的做法中，每次01背包操作要对0~V整个空间遍历，01背包的操作次数与物品数量线性相关，时间复杂度O(V∑si)。
所以在物品数量很多、背包空间很大时，时间复杂度会很高。
单纯的01背包问题难以优化，而多重背包具有其特殊性，根据每种物品有si个借题发挥，可以进行优化。

优化1:二进制优化。
例如某种物品有63个，朴素法需要63次01背包操作，
对于空间0~V的每个位置，放1个试试取max，
对于空间0~V的每个位置，放1个试试取max，
对于空间0~V的每个位置，放1个试试取max，
对于空间0~V的每个位置，放1个试试取max，
...
...
重复63次。

而63二进制可以表示为(111111)2，所以1、2、4、8、16、32的所有组合情况，相加就能获得0 ~ 63之间的每个数。
对于空间0~V的每个位置，放1个试试取max，
对于空间0~V的每个位置，放2个试试取max，
对于空间0~V的每个位置，放4个试试取max，
...
...
对于空间0~V的每个位置，放32个试试取max，
重复6次。

二进制优化后时间复杂度从O(V∑si)变为了O(V∑logsi)

优化2：单调队列优化。
该单调队列中的元素是指f[j]中的背包空间j，并且每个相邻元素之间相差v空间，v是物品大小。
窗口长度为物品个数，f[j] = max(f[j],f[j - k*v] + k*w)，
队列中每个元素通过增加若干个物品v后，占用背包空间都变为j时，价值的大小，据此构建单调队列。

这里其实有一个小问题，当窗口移动一格后，单调性的判断
从
f[j] = max(f[j],f[j - k*v] + k*w)
变为了
f[j + v] = max(f[j + v],f[j + v - k*v] + w + k*w)。
队首是否仍然是“最值”。
这里有点类似dijkstra最短路的思想，整体的最佳方案，必然要求局部的最佳方案，不可分割。
这里理解不太透彻，只会意会，不会言传。

好麻烦，以后再说吧。
优化后时间复杂度从O(V∑si)变为了O(V)。