单调队列与DP

简介

单调队列是一种特殊的双端队列，其内部元素具有单调性。

单调队列有以下两种操作：

1. 插入：新元素从队尾插入时会破坏单调性，则删除队尾元素，知道找到插入后不破坏单调性的位置，将该元素插入到队尾。
2. 获取最大（最小）值：访问队首元素。

一般来说单调队列优化DP时每个元素一般存两个值：

1. 它在原数列中的位置；
2. 它在DP中的状态值。

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

在C++中可以使用deque这个双端队列的数据结构。它的操作包括了pop（弹出队首），pop_back（弹出队尾），push_back（插入队尾），push_front（插入队首）等。

问题引入：

给定一个数列a[1],a[2],...,a[n]，求每一个f(i)，其中f(i)=min{a[j]},j=i-m+1,i-m+2,...,i。即对数列中每段长为m的区间，找到这段区间的最小值。

这就是滑动窗口问题。

我们维护一个队列，队列中每个元素有两个值pos,val表示位置和值。

在计算f[i]时，只要在队首不断删除，直到队首的pos≥i-m+1，此时队首的val必定是f[i]的最佳选择，因为队列是单调的。

考虑如何插入a[i]：为了保证队列单调性，插入a[i]时需要向前扫描，将队尾元素不断删除，直到队尾元素小于等于a[i]。

显然每个元素最多进出队各1次，所以时间复杂度是O(n)。

DP中的单调队列应用往往涉及定长连续子区间的最值问题，也涉及很多特殊的建模技巧。

例题

1. 滑动窗口

法一：暴力，时间复杂度O(nk)。

法二：区间查询问题，线段树/ST表，时间复杂度O(nlogk)。

法三：单调队列，注意到本题查询区间等长，在查询[l,r]区间时，除非最值落在a[l-1]，否则只需要将[l,r-1]区间内的最值和a[r]比较即可。

也就是说，对任意l≤i<j≤r，如果a[i]<a[j]，那么a[i]就一定没用了，因为能用a[i]时一定能用a[j]。这个性质就和单调队列的性质吻合了。

因此当我们将区间从[l,r]移动到[l+1,r+1]时，若队首不在[l+1,r+1]中，则将其删除然后将a[r+1]插入，这样的队首就是[l+1,r+1]内最大值。

时间复杂度O(n)。

---

2. 最大连续和

法一：直接DP。

设dp[i]表示以a[i]结尾的长度不超过m的最大子序列和，则

dp[i]=max(sum(a[j]),j=i-m+1,i-m+2,...i)。

对每个dp[i]枚举k，总时间复杂度O(nm)。

法二：堆优化DP。

令s[i]=sum(a[j]),j=1,2,...,i为数组a的前缀和，则

dp[i]=max(s[i]-s[i-k],k=1,2,...,m)=s[i]-min(s[i-k],k=1,2,...,m)。

所以可以用一个二叉堆来维护s[i-k]。

每次求dp[i]之前的操作如下：

1、在堆中删除s[i-m-1]，插入s[i-1]，时间复杂度O(2logn)；

2、从堆中找到最小值，时间复杂度O(1)； 故总复杂度O(nlogn)。

法三：单调队列优化。

我们改用队列维护s[i-k]，每一步在队首删除s[i-m-1]，队尾添加s[i]。

但这样还是O(nm)，需要进一步优化，先考察s的性质。

1. 考虑添加s[i-1]时，假设队尾是s[k]，由于k<i-1，所以s[k]必然比s[i-1]先出队，则s[k]在之后永远用不到，就是说可以删除s[k]。
2. 对于队列中两个元素s[i]和s[j]，如果i<j且s[i]≥s[j]，则我们可以删掉s[i]，因为这个数已经用不上了。那么队列中元素和下标都递增，是单调队列。

最终算法步骤：

1. 若队首s[x]有x<i-m，则s[x]出队，直到x≥i-m；
2. 若队尾s[k]有s[k]≥s[i-1]，则s[k]出队，直到s[k]<s[i-1]；
3. 在队尾插入s[i-1]
4. 取出队首元素。

由单调队列优化DP的时间复杂度知该算法时间复杂度为O(n)。

---

3. 修剪草坪

状态：dp[i][0]表示以i结尾且不选i的最大效率值；dp[i][1]表示以i结尾并且选i的最大效率值。

转移：

• dp[i][1]=max(dp[j][0]+sum[i]-sum[j]),i-k≤j<i

• dp[i][0]=max(dp[i-1][0],dp[i-1][1])

可以将dp[i][1]的方程变形为：

dp[i][1]=max(dp[j][0]-sum[j])+sum[i],i-k≤j<i

这样就可以用一个长度为k的单调队列来维护dp[j][0]-sum[j]了。

---

4. 旅行问题（单调队列在非DP问题的应用）

法一：朴素算法

直接枚举每个车站为起点然后模拟，时间复杂度O(n2)。

法二：堆优化

我们先考虑顺时针的情况。令a[i]=p[i]-d[i]表示我们从i到i+1号车站的油量变化，然后我们将环拆开变成一条长为2n-1的链，满足a[n+i]=a[i]。再令sum[i]表示a[i]的前缀和，那么我们可以看出来，要判断从某个车站i出发能否周游一圈，就是判断sum[i]-sum[i-1],sum[i+1]-sum[i-1],...,sum[i+n-1]-sum[i-1]这n个数中是否存在负数，如果有负数，则表示中途一定会出现没油的情况，否则可以顺利行驶一周。

也就是说，我们可以直接查询这n个数中的最小数来判断能否周游一圈。所以可以使用一个堆来存储这n个数，当然我们插入堆的时候只需要插入sum[i]，然后判断第i个点的时候取出最小值然后减去sum[i-1]即可。然后随着起点的变化，我们需要相应将sum[i]删除并插入sum[i+n]，总时间复杂度O(nlogn)，本题数据范围可过。

堆优化可以直接写优先队列。

法三：RMQ

注意到我们的问题可以写成：给一个数列sum[1..2n-1]，还有n个区间[l1,r1],...,[ln,rn]，每个区间满足1≤li≤n，li+n-1=ri。对每个区间找最小值。

这个问题就显然可以套用标准RMQ算法来解决了。但是RMQ算法的变成复杂度比较高。

法四：单调队列优化

在使用单调队列之前，我们需要先证明n个最小值的编号满足单调性。

考虑堆优化的执行过程，我们可以发现，如果删除的sum[i]和插入的sum[i+n]都很大，对堆中的最小数是没有影响的。所以，如果在某一段sum[i],sum[i+1],...,sum[i+n-1]中，如果存在j<k使得sum[j]>sum[k]，则sum[j]就永远不可能成为最小值。因此n个最小值的编号也满足单调性，可以使用单调队列进行优化。

具体算法如下：

1. 对sum[i]维护一个单调队列；
2. 当以i为起点时，若队首的id<i则删除，直到队首的id≥i；
3. 若队尾的元素比待插入的元素sum[i+n-1]大，则该元素不可能成为最小值，从队尾删除，直到队尾元素小于sum[i+n-1]，在队尾插入sum[i+n-1]；
4. 若队首元素不小于sum[i-1]，则表示从i出发可以成功行驶一周。
5. 对逆时针的情况再处理一次即可。

时间复杂度O(n)。

---

5. Banknotes（单点队列优化多重背包）

法一：套用01背包

将c[i]枚面值为b[i]的硬币拆成c[i]个物品，直接跑01背包，时间复杂度O(n*sum(c[i]))。

法二：二进制优化（在讲背包的时候讲过）

将c[i]枚面值为b[i]的硬币使用二进制拆分拆成2的次幂的和，如13=1+2+4+6，再跑01背包，时间复杂度O(n*sum(log c[i]))。

法三：单调队列优化

对当前面值b[i]，根据容量模b[i]的余数分为b[i]块，每块内前后两状态差b[i]，所以j*b[i]+d状态的最优值从(j-l)*b[i]+d,l=1...k里来。

单调队列优化的时间复杂度是O(nk)，但由于常数较大，很多情况下不如二进制优化快。