Sliding Window Maximum
你会得到一个整数数组 nums 和一个窗口大小 k。由 k 个连续值组成的窗口从最左端开始，每次向右移动一个位置，直到窗口右边缘到达最后一个值。按从左到右的顺序，返回窗口在每个位置上的最大值：对于长度为 n 的数组，共有 n-k+1 个值。
函数
- numsinteger-array
- 窗口滑过的数组
- kinteger
- 每个窗口中的值的数量
- 返回值integer-array
- 每个窗口中的最大值，从最左侧窗口到最右侧窗口
约束条件
1 ≤ k ≤ nums.length ≤ 2 × 104-104 ≤ nums[i] ≤ 104- 结果包含
nums.length-k+1个值，每个窗口对应一个，按从左到右的顺序排列。
示例
- 输入
- nums = [4, 2, 12, 3, 8, 5, 1]k = 3
- 输出
- [12, 12, 12, 8, 8]
- 解释
- 12 位于最初的三个窗口中，因此每个窗口的答案都是 12。12 滑出后，
[3, 8, 5]和[8, 5, 1]的最大值都是 8。
- 输入
- nums = [-3, -1, -7, -2]k = 2
- 输出
- [-1, -1, -2]
- 解释
- 这些区间分别是
[-3, -1]、[-1, -7]和[-7, -2]。两个负数中较大的那个离 0 更近，因此结果是 -1、-1 和 -2。
- 输入
- nums = [6, 6, 1]k = 3
- 输出
- [6]
- 解释
- 当
k等于数组的长度时，只有一个窗口，也就是整个数组。它的最大值是 6，第二个 6 不会产生另一个答案。
进阶
你能构建一个队列，支持在队尾添加一个值、移除队首的值，以及读取当前最大值，并且每项操作的均摊时间复杂度都是 O(1) 吗？
提示
逐个打开提示，每个都会多透露一点。
扫描每个窗口以找出其中的最大值，每个窗口需要
k步。比较两个相邻窗口：它们共享k-1个值，因为左侧有一个值离开，右侧有一个值进入。当一个新值进入时，窗口中所有小于或等于它的旧值都不可能再成为最大值。在之后仍包含旧值的每个窗口中，新值都会保留，而且它至少和旧值一样大。你可以彻底丢弃这些旧值。
在双端队列中保留仍有效的值的索引，并确保这些值从队首到队尾严格递减。对于每个新索引，从队尾弹出较小或相等的值，再将该索引压入队列；如果队首已滑出窗口，就将其移除，然后读取队首的值作为窗口最大值。
题解
相邻窗口共享 k-1 个值，因此重新计算每个最大值会重复几乎所有工作。但最大值无法撤销：当最大的值滑出窗口时，你需要找到次大的值，而不必重新读取整个窗口。单调双端队列只保留仍有可能成为最大值的值，答案就在队首。
扫描每个窗口
结果正确，但无法在最大的测试中运行完毕
思路
读取每个窗口的 k 个值，并保留其中最大的值。每个窗口都会被完整读取，因此不会漏掉其中的最大值。n-k+1 个窗口中的每个窗口都需要读取 k 次，最坏情况出现在 k 约为 n 的一半时：n = 2 × 10^4 且 k = 10^4 时，约有 10^4 个窗口，每个窗口有 10^4 个值，共需读取 10^8 次。
算法
- 让
start从 0 循环到n-k。 - 取
nums[start]到nums[start+k-1]中的最大值。 - 将它追加到结果中，并在循环结束后返回结果。
def maxSlidingWindow(nums, k):
result = []
for start in range(len(nums) - k + 1):
# Read all k values of this window again
result.append(max(nums[i] for i in range(start, start + k)))
return result每一侧的最大区块
思路
将数组划分为长度为 k 的块：索引从 0 到 k-1，然后从 k 到 2k-1，依此类推。如果 k 不能整除 n，最后一块会更短。窗口的长度恰好是 k，因此它要么是一个完整的块，要么由一个块的末尾和下一个块的开头组成。
因此，预先计算 fromStart[i]，即从 i 所在块的开头到 i 的最大值；以及 toEnd[i]，即从 i 到所在块末尾的最大值。以 i 为起点的窗口在 i+k-1 处结束：toEnd[i] 覆盖窗口左侧部分，fromStart[i+k-1] 覆盖右侧部分，两者中较大的值就是窗口的最大值。在第一个示例中，窗口 [2, 12, 3] 取 toEnd[1] = 12 和 fromStart[3] = 3，因此最大值为 12。
通过三次遍历，时间复杂度为 O(n)，代价是需要两个长度为 n 的辅助数组，并且必须先获取整个数组才能得到第一个答案。
算法
- 从左到右填充
fromStart，当i是k的倍数时，重新从nums[i]开始。 - 从右到左填充
toEnd，在最后一个索引处以及i+1是k的倍数的位置，重新从nums[i]开始。 - 对于从 0 到
n-k的每个起始位置i，追加toEnd[i]和fromStart[i+k-1]中较大的值。
def maxSlidingWindow(nums, k):
n = len(nums)
# Cut nums into blocks of k: indices 0..k-1, k..2k-1, and so on.
from_start = [0] * n # max from the start of i's block up to i
to_end = [0] * n # max from i up to the end of i's block
for i in range(n):
if i % k == 0:
from_start[i] = nums[i]
else:
from_start[i] = max(from_start[i - 1], nums[i])
for i in range(n - 1, -1, -1):
if i == n - 1 or (i + 1) % k == 0:
to_end[i] = nums[i]
else:
to_end[i] = max(to_end[i + 1], nums[i])
# A window [i, i+k-1] is the tail of one block plus the head of the next.
return [max(to_end[i], from_start[i + k - 1]) for i in range(n - k + 1)]单调索引双端队列
思路
如果索引 j 在 i 之前，且 nums[j] ≤ nums[i]，那么 j 再也不可能成为最大值：之后所有包含 j 的窗口也都包含 i，而 i 离开得更晚。因此，i 到来时，你可以忘掉 j。
用双端队列保存尚未忘掉的索引。i 到来时，只要队尾索引对应的值小于或等于 nums[i]，就从队尾弹出该索引，然后将 i 入队。剩余的值从队首到队尾严格递减，因此队首就是窗口中的最大值。要保存索引，因为窗口越过队首索引时，也必须将它移出队列。在第一个示例中，索引 5 处的双端队列中有 12、8 和 5；12 位于索引 5 - 3 = 2，因此它会离开，答案是 8。
每个索引只入队一次，最多出队一次：双端队列操作最多有 2n 次，时间复杂度为 O(n)。双端队列中最多保存 k 个索引。
算法
- 对于每个索引
i，只要双端队列不为空，并且队尾的值小于或等于nums[i]，就从队尾弹出索引。 - 将
i推入队尾。 - 如果队首索引等于
i-k，说明它已经离开窗口：将它弹出。 - 当
i ≥ k-1时，将队首索引对应的值追加到结果中。
from collections import deque
def maxSlidingWindow(nums, k):
window = deque() # indices; their values strictly decrease from front to back
result = []
for i, x in enumerate(nums):
# A value at the back that is not bigger than x can never be a maximum again.
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
# The front index has slid out of the window on the left.
if window[0] == i - k:
window.popleft()
# From index k-1 on, every step completes a window; its maximum sits at the front.
if i >= k - 1:
result.append(nums[window[0]])
return result
易错点和边界情况
- 存储值而不是索引。对于
[3, 1, 3]和k = 2，第二个 3 会弹出第一个 3，然后因为它等于nums[0]（离开窗口的值），所以它自身也会被移除。 - 过早或过晚给出答案。第一个完整窗口在索引
k-1处结束，结果必须恰好包含n-k+1个值。 - 移除
i-k+1而不是i-k。该索引对应的值仍是窗口中的第一个值。 - 读取双端队列末尾的值时，没有检查队列是否为空。
- 在分块方法中，忘记最后一个块可能短于
k。从右向左遍历时，除了每个块的末尾，还必须从最后一个索引处重新开始。
常见问题3
滑动窗口最大值的时间复杂度是多少？
单调双端队列解法的运行时间为 O(n)，因为每个索引只会入队一次，出队次数最多为一次。双端队列最多保存 k 个索引，因此除结果所占空间外，额外空间复杂度为 O(k)。
可以用堆解决滑动窗口最大值问题吗？
是的。将值和索引组成的对推入最大堆，并在读取堆顶元素之前，只要其索引超出窗口范围就将其弹出。这样运行需要 O(n log n) 时间，最多可容纳 n 个条目。双端队列更快、占用空间更少，因为一旦出现更大的值，它就会立即丢弃无用的值。
单调双端队列和单调栈有什么区别？
双端队列的末端像单调栈一样工作：推入一个值之前，先弹出它使之失去作用的值。双端队列还在前端增加了一个出口，用来移除过期的值。下一个更大元素不会过期，因此只需要用栈。反转比较条件，双端队列就能得到每个窗口的最小值。
def maxSlidingWindow(nums, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [4, 2, 12, 3, 8, 5, 1] k = 3
预期输出
[12, 12, 12, 8, 8]