简介

本题的标签是Heap，Sliding Window和Dequeue，是滑动窗口和双端队列结合的一道经典题。本文将着重讲解双端队列解法，同时对动态规划的解法进行简单的讲解。

注意：文章中一切注解皆为Python代码

理解题目

题目非常简单。给定一个数列，和一个窗口，在窗口从左向右滑动的时候，持续计算窗口中子数列的最大值。

最暴力的解法就是在窗口滑动的过程中持续计算最大值，代码就一行，如下

class Solution:    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':        return [max(nums[i-k:i]) for i in range(k, len(nums)+1)]

很明显，暴力解法需要的时间复杂度是O(NK)，其中N是数据规模，K是窗口大小。如果窗口大小K等于N/2的话，时间复杂度可以表示为O(N^2)。对于题目中输入范围为10⁵ 这种级别，显然O(N^2)这种时间复杂度是不行的，因此需要探索其他解法。

题目剖析+思考过程

想到更优的解法其实并不难，首先我们要意识到这题的两个操作，一是遇到新数字时对当前最大值的更新，二是淘汰过期数字时对当前最大值的更新。

对于第一种情况，我们都知道一个前缀数组(prefix array)就可以解决。那么如何去淘汰过期的数字，并更新最大值呢？显然单纯的前缀数组不好使了，怎么办：

首先，提到“过期”可能最先想到的就是队列(queue)，先进先出

其次，淘汰“过期”数字后，需要选出第二大的数字，依次类推，可能还需要第三、第四、第K大的数字

那什么样的数据结构可以高效的提供这样（内容不断变化且能保持一定顺序）的信息呢？

堆(heap)就可以

单调递减的双端队列也可以

堆

这里的堆(heap)很好理解，堆的加入和删除都仅仅耗费O(logK)，并且，它时时刻刻能保证顺序；最终的时间复杂度可以近似为O(NlogN)。

那么如何去理解单调递减的双端队列呢？

单调递减双端队列

双端队列本身不用多讲，先进先出，两端都可以以O(1)的时间加入和删除；对于单调递减，我们事实上是为了维护一种单调递减的顺序，也就是之前我提到的

淘汰“过期”数字后，需要选出第二大的数字，依次类推，可能还需要第三、第四、第K大的数字

这本质上是一种单调递减的状态，看个例子：

给出数列[9,5,7,6,11]，窗口长度为3，起初单调递减队列dq为空，指针i = 0

i = 0, dq = [9], 当前max = 9, 窗口中数列为[9], 滑动最大值还未开始计算，因为窗口内数组不满3个

i = 1, dq = [9, 5], 当前max = 9, 窗口中数列为[9, 5], 滑动最大值还未开始计算，因为窗口内数组不满3个

i = 2, dq = [9, 7], 当前max = 9, 窗口中数列为[9, 5, 7], 滑动最大值[9]；
- 注意为了保证队列的单调递减性，之前的5被弹出来，7加了进去
- 因为只要7还有没有过期，7肯定比5大
- 而且7在5之后，肯定比5要更晚过期

i = 3, dq = [7, 6], 当前max = 7, 窗口中数列为[5, 7, 6], 滑动最大值[9, 7]
- 注意这里9已经失效，被从左端弹出
- 按照单调递减的已有顺序，我们自然的把下一个数字，即7，当作当前最大值

i = 4, dq = [11], 当前max = 11, 窗口中数列为[7, 6, 11], 滑动最大值[9, 7, 11]
- 这里5过期失效，但是5不是当前最大值，7才是，所以5的离开对单调递减双端队列没有任何影响
- 接着11被加入队列，为了保证单调递减性，6和7被依次从右端弹出，最终加入11

最终得到的结果为[9, 7, 11]

我想上面的过程你可能已经理解了，但是这里再强调一下，这题“巧妙”的部分在于，把单调性和双端队列结合起来了。一般算法题中更为常见的是，单调性和栈的结合，即单调栈(Monotonic Stack)，比如另一道经典题。

人们对于没有见过的事物总是会感到恐惧，学生对于没有练习过的题目总会感到无从下手，这大概就是本题最优解的难点所在吧。

代码实现（附注释）

堆

class Solution:    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':        ans, heap, n = [], [], len(nums)        for i in range(n):            heapq.heappush(heap, (-nums[i], i))  # 在heap中加入一个tuple(值，指针)            while heap and heap[0][1] + k <= i:  # 如果值对应的指针过期的话，                heapq.heappop(heap)              #     就heappop直到找到没有过期的为止            if i >= k-1:                         # 一旦窗口内元素达到K个，就开始计算滑动最大值                ans.append(-heap[0][0])          # 值是按负数存进去的，模拟的是最大堆maxheap        return ans

单调递减双端队列

因为每个数字最多被访问两次，所以最终的时间复杂度是O(N)，空间复杂度是O(N-K+1)

class Solution:    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':        dq, ans, n = collections.deque(), [], len(nums)        for i in range(n):            while dq and nums[i] > dq[-1]:    # 在加入新数字前，弹出比当前值小的数字，                dq.pop()                      #     以确保加入后的单调递减性            else:                    dq.append(nums[i])            # 上面的循环完成后，加入新数字            if i >= k and nums[i-k] == dq[0]: # 如果当前要被淘汰的数字nums[i-k]是双端队列的左端点，                dq.popleft()                  #     即说明，当前最大值过期要被淘汰掉，从左侧弹出队列            if i >= k-1:                      # 一旦窗口内元素达到K个，就开始计算滑动最大值，                ans.append(dq[0])             # 	最大值永远是单点递减双端队列的左端点        return ans

动态规划解法

本题的最优解是单调双端队列的解法，但是为了完整性，这里提一下同样巧妙的动态规划解法。

之前提到过前缀数组可以很好的计算当前最大值，但是没法帮助我们处理淘汰数字后的情况；动态规划的解法用到了一左一右，两个前缀数组，以及数学上的一种巧思。

设问我们要怎么知道给定一小段窗口中的最大最小值呢？显然你可以暴力算一遍，这不是我想讲的。提示一下，给一个从左到右的最大前缀数组，和一个从右到左的最大前缀数组，可以算出来吗？

好像不行，因为无论从左到右还是从右到左，都有可能包含已经过期的值。那进一步去想，如何在此基础上处理过期数据呢？有什么方法可以让前缀数组包含是否过期的信息呢？

答案就是分段。把前缀数组按照每K个一组去分段，每一段从新开始计算最大值，这样一来：

左前缀数列的最右端包含的最大值仅仅作用于K个数据

右前缀数列的最左端包含的最大值仅仅作用于K个数据

比较这两个值就可以得出这一段的最大值

LeetCode的官方解法说的很好，这里就不多解释了，总之：两个前缀分段数组。

解法的实现上我稍微优化了一下，看起来更直截了当

class Solution:    def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':        n = len(nums)        left, right = [0] * n, [0] * n        left[0], right[n-1] = nums[0], nums[n-1]        for i in range(1, n):            if i % k == 0:                            # 计算左前缀数列                left[i] = nums[i]            else:                left[i] = max(left[i - 1], nums[i])            j = n - i - 1            if (j + 1) % k == 0:                      # 计算右前缀数列                right[j] = nums[j]            else:                right[j] = max(right[j + 1], nums[j])                                                      # 比较两者取最大值        return [max(left[i + k - 1], right[i]) for i in range(n - k + 1)]