重新发明单调队列——滑动窗口求最值问题如何解？

Sunbread · 2019-12-12 06:47:40 · 个人记录

单调队列可用于求解滑动窗口求最值问题。本文可以指引你重新发明一遍单调队列。

要求解滑动窗口求最值问题，我们可以想到一个很朴素的解法：对每个滑动窗口里面的所有元素都求一遍最值。

朴素解法虽然空间复杂度为O(1)（这里不考虑输入的空间复杂度，下文亦同），但时间复杂度为O(nk)，在滑动窗口长度处于特定范围时算法所耗时间会变得无法承受。

接下来我们思（hu）考（gao）一种新的解法，降低时间复杂度，允许空间复杂度提升。

单调序列

我们首先建立一个空的序列A，假设这个序列允许在常数时间内插入、删除和查询任一元素。这样的序列在OI常用算法中并没有对应的线性表实现，不过我们可以推迟考虑算法的实现，先假设有这么一个序列。

接下来，我们遍历一遍问题序列的每一个元素，不妨设为x，并进行如下操作：

不难发现，每一次操作结束后A的两端元素始终都是滑动窗口内的最值。

这个方法时间复杂度为O(nk)（遍历问题序列需要n次；每一次遍历中找到一个位置插入x最坏时间复杂度为O(k)，遍历A中所有元素时间复杂度为O(k)），空间复杂度为O(k)。看起来不仅时间复杂度没有优化，空间复杂度也提升了。这不是一个好方法，但我们可以考虑优化一下。

因为单调序列是单调的，我们可以考虑使用二分查找确定x插入的位置。

我们可以优化一下遍历A中所有元素的步骤。

众所周知，从一个单调序列中任意删除元素，序列仍然保持单调的性质。

因此，我们可以在每次遍历问题序列时只删除A两端连续的离开滑动窗口的元素，这样删除后A两端的元素仍然是滑动窗口内的最值。

遍历问题序列需要n次，每一次遍历A中找到一个位置插入x所需时间复杂度为O(\log{k})。

惰性删除元素确保在整个算法中删除离开滑动窗口的元素时几乎只遍历到要删除的元素，而问题序列中的每一个元素在整个算法中最多从A删除一次，因此所需时间复杂度为O(n)。

二分查找优化对空间复杂度没有影响。惰性删除元素允许A长度比k长，但仍然长不过n，所以空间复杂度为O(n)。

因此，使用这两个优化的单调序列求最值所需时间复杂度为O(n\log{k})，空间复杂度为O(n)。经过优化后这个方法效率比朴素解法要好多了。

在论证完上述解法的步骤和复杂度之后，我们就得考虑之前推迟考虑的解法实现了。

这个解法有一个明显的问题：为了实现序列A，这个算法需要一个在常数时间内插入、删除和查询任一元素的线性表，然而OI常用数据结构中并没有这样的数据结构。

为了解决这一问题，我们可以给问题加上更强的限制，这样解法所用到的序列可能就会变成更简单的形式。与此同时，算法的复杂度可能也会跟着减少。

为了找到一个合适的能用于建立A的数据结构，以及达到更低的时间复杂度，我们可以考虑给问题做一个更强的限制，比如说只求最大值/最小值。下文以最大值为例。

我们构造一个单调序列，不妨构造一个单调递减序列，这样滑动窗口内最大值就在这个单调递减序列的最前面。这样，最后面的值就没用了，我们可以考虑从这里入手。

在维护单调序列的过程中，我们需要找到一个位置向A插入x以使序列保持单调。然而由于最后面的值没用了，我们可以考虑直接抛弃x后面的元素。

具体做法是：在单调递减序列中，从后往前遍历，把找到的所有不大于x的元素都删除掉，然后把x附加在序列的后边。

这么搞之后最后面的值就失去在问题序列上的意义了，因此惰性删除元素要改成只删除A前面连续的离开滑动窗口的元素。

经过魔改后的单调序列在遍历问题序列时的操作就变成了：

不难发现，每一次操作结束后A的第一个元素始终都是滑动窗口内的最大值。

这样，我们就解决了滑动窗口求最大值的问题。求最小值则只需维护一个单调递增序列，其余步骤自行对应。

与前面章节提出的无法实现的序列A相比，魔改后算法中的序列A完全可以用一个双端队列实现，双端队列允许在常数时间内对头尾的附加、删除和查询。因此，这种可以用双端队列实现的单调序列就被命名为单调队列。

因为问题序列的每个元素只进出A一次，而且每个元素出队所对应的判断都只消耗常数时间，因此单调队列的时间复杂度是O(n)。虽然单调队列只能判断一个最值，但我们可以同时维护两个单调队列，一个求最大值，一个求最小值即可。

空间复杂度没有得到优化，仍然是O(n)。

相比需要依赖于无法实现的数据结构的单调序列，单调队列更容易实现，只需要一个双端队列就可以了。

本文带你重新发明了一遍单调队列。相信在看完这篇文章，认真思考之后，你会对单调队列（和胡搞法）有更深的理解。

勘误致谢：