单调队列DP优化

本文总阅读量次

一、名词解释

队列
跟生活中的排队一样，队头负责出，队尾负责进。
单调队列
一种严格单调的队列（严格递增或者递减），其中队列中元素的位置也有一定的递增递减的性质。队首位置保存的是最优解，接着次优解。
双端队列
队列两端都可以进行入队或出队操作，单调队列优化就是一种双端队列。

二、单调队列求最大连续和

题目传送门
题目大概描述
给定一个长度为 $N$ 的整数序列(可能有负数)，从中找出一段长度不超过 $M$ 的连续子序列，使得子序列中所有数的和最大。 $N, M <= 3 * 10^{5}$
也就是要寻找区间 $[i, j]$ ，使得 $a_{i} + a_{i + 1} . . . + a_{j}$ 的和最大。
解法1
前缀和做预处理，暴力搜索区间，时间复杂度 $O (N^{2})$
解法2
贪心
策略：当前连续相加的和如果是负数则断开，即遇到了一个很大的负数，它没有加的价值，不会使得当前这段序列的和更大，也不会使后面序列的和更大。时间复杂度 $O (N)$ .
解法3
单调队列
把前缀和放入到单调队列中，当第 $i$ 个位置的时候，符合区间长度的位置中，寻找一个前缀和最小的，这样当前位置的前缀和减去区间内前缀和最小的，才能让区间和最大。
单调队列的一般步骤：
1.枚举： $i$ 作为右端点。因为连续子序列长度不超过 $m$ ，所以枚举 $i$ 的时候，队头元素的位置和 $i$ 的距离不能大于 $m$ 。如果超出范围了，则出队，直到符合距离要求。符合要求的距离在区间[i-m+1,i-1]
2.这个时候队头就是右端点为 $i$ 时的最优解。
3.然后当前第 $i$ 个前缀和要入队，但是要满足队列的单调性，所以当前队尾的元素要小于 $s [i]$ (这里用 $s$ 表示前缀和数组)，如果队尾元素大于 $s [i]$ ，则出队，直到满足单调性。

    int head=1,tail=1;  //队头队尾指针
    ans = -2e9;
    for(int i = 1; i <= n; i++){ //枚举右端点i
        while(head<=tail && i - pos[head] > m) ++head; //距离超过m的出队
        ans = max(ans,f[i]-f[pos[head]]); //当前队头是以右端点为i时的最优选择
        while(head<=tail && q[tail] >= f[i]) --tail; //调整单调性，使得能放入f[i]为止
        pos[++tail] = i; //入队：位置
        q[tail] = f[i];  //入队：前缀和
    }

两个 $w h i l e$ 都是对队列的调整，一个是长度调整，一个是单调性调整。
为什么说以 $i$ 为右端点时，队头是最优选择。因为单调队列是从小到大排列的，队头是前缀和最小的，那么减去最小的前缀和，就得到了最大的连续和。

三、单调队列DP优化

注意，单调队列DP优化，并不像之前学的一些基础DP那样属于某种类型(背包、坐标型、区间型等等)。它其实是用单调队列对动态规划进行优化，往往能把一个时间复杂度为 $O (N^{2})$ 的算法，降低为 $O (N)$ ，因为每个元素队列中只进出一次。
单调队列的模板就是类似上面这段代码，区别就是条件不同。使用的难度还是在思维上。
引用算法进阶的一句话：它的思想是在决策集合(队列)中及时排除一定不是最优解的选择。
我补充一句：决策集合(队列)必须符合单调性。