夜雨聆风AI 横行的时代，算法岗依然需要现场 coding 的能力，该栏目将持续分享力扣原题。温故而知新，既然刷到了，就停下来复习一下再划走吧。
239. 滑动窗口最大值
给定一个整数数组 nums，一个大小为 k 的滑动窗口从数组最左侧开始，每次向右移动一个位置。题目要求返回每个窗口中的最大值。
例如，输入 nums = [1, 3, -1, -3, 5, 3, 6, 7]、k = 3，窗口移动过程如下：
[1, 3, -1]，最大值为3；[3, -1, -3]，最大值为3；[-1, -3, 5]，最大值为5；[-3, 5, 3]，最大值为5；[5, 3, 6]，最大值为6；[3, 6, 7]，最大值为7。
因此最终返回 [3, 3, 5, 5, 6, 7]。
这道题的难点不在于计算一个窗口的最大值，而在于窗口移动以后，如何快速得到新窗口的最大值。如果每次都重新遍历窗口，需要 O(k) 的时间；而使用单调队列，可以把每次移动的均摊成本降到 O(1)。
第一种：逐个窗口查找最大值（会超时）
最直接的做法是枚举每个长度为 k 的窗口，然后使用 max 找出窗口内的最大值。
from typing import List
classSolution:
defmaxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
window_maximums = []
array_length = len(nums)
for window_start in range(array_length - k + 1):
window_end = window_start + k
current_maximum = max(nums[window_start:window_end])
window_maximums.append(current_maximum)
return window_maximums
长度为 n 的数组中，一共有 n-k+1 个窗口。每个窗口都要截取 k 个元素并寻找最大值，因此时间复杂度为 O((n-k+1)k)，通常可以简化为 O(nk)。
这种方法逻辑简单，但相邻窗口之间存在大量重复计算。比如窗口从 [1, 3, -1] 移动到 [3, -1, -3] 时，元素 3 和 -1 仍然留在窗口中，却被重新比较了一遍。
时间复杂度 O(nk)，空间复杂度 O(k)。如果不计算切片产生的临时空间，则额外空间为 O(1)。
第二种：单调队列（推荐写法）
要减少重复计算，需要在窗口移动时保留仍然有效的最大值候选。这里可以使用一个从队首到队尾对应元素值单调不增的双端队列。
队列中不直接保存元素值，而是保存它们在数组中的下标。这样既能通过 nums[index] 比较大小，也能判断队首元素是否已经离开当前窗口。
from typing import List
from collections import deque
classSolution:
defmaxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
window_maximums = []
candidate_indices = deque()
for current_index in range(len(nums)):
# 移除队尾所有小于当前元素的候选
while (
candidate_indices
and nums[candidate_indices[-1]] < nums[current_index]
):
candidate_indices.pop()
candidate_indices.append(current_index)
# 移除已经离开当前窗口的队首下标
window_left = current_index - k + 1
if candidate_indices[0] < window_left:
candidate_indices.popleft()
# 窗口形成后，队首就是当前窗口最大值
if current_index >= k - 1:
maximum_index = candidate_indices[0]
window_maximums.append(nums[maximum_index])
return window_maximums
这段代码主要完成三件事：维护单调性、删除过期元素，以及读取窗口最大值。
1. 为什么要从队尾删除较小元素
处理 nums[current_index] 时，如果队尾下标对应的元素比当前元素小，就将它从队列中删除。
原因是当前元素同时具备两个优势：
当前元素更大； 当前元素的位置更靠右，因此会更晚离开窗口。
例如，当前队列对应的元素是 [5, 3]，新元素是 6。在后续包含 6 的窗口中，5 和 3 都不可能成为最大值，因为 6 比它们更大，而且比它们更晚过期。因此可以直接将它们从队尾删除。
经过处理后，队列对应的元素始终保持单调不增，队首自然就是当前窗口内最大的候选值。
代码中使用的是 nums[candidate_indices[-1]] < nums[current_index]，因此遇到相等元素时，会同时保留它们的下标。这种写法没有问题：较早的相同元素过期后，较晚的相同元素仍然可以继续作为最大值。
如果改成 <=，也同样正确。此时会删除较早出现的相同元素，只保留位置更靠右的那个，因为它能够在窗口中停留更久。
2. 为什么队列中必须存下标
如果队列只保存元素值，就无法判断一个元素是否已经随着窗口移动而离开。
当前窗口的左边界为 current_index - k + 1。如果队首下标小于这个左边界，说明它已经不在当前窗口中，需要从队首删除。
例如，窗口大小 k = 3，当前遍历到下标 4，那么当前窗口覆盖的下标范围是 [2, 4]。此时任何小于 2 的下标都已经过期。
因此，存储下标能够同时解决两个问题：
根据下标访问对应元素，维护单调性； 根据下标判断元素是否离开窗口。
3. 为什么队首一定是最大值
队列中的下标按照进入顺序排列，其对应元素值则保持单调不增。因此，队首对应的元素一定不小于队列中的其他元素。
同时，程序会及时删除已经离开窗口的队首下标，所以队首元素始终属于当前窗口。当窗口长度达到 k 后，直接读取 nums[candidate_indices[0]]，就是当前窗口最大值。
复杂度分析
虽然代码中存在一个 while 循环，但时间复杂度并不是 O(n²)。
每个数组下标最多执行两次队列操作：
进入队列一次； 从队首或队尾离开队列一次。
某个下标一旦被删除，就不会再次进入队列。因此，所有 while 循环在整个程序中的执行次数累计不会超过 n，总时间复杂度为 O(n)。
队列中最多保存当前窗口中的 k 个下标，所以空间复杂度为 O(k)。
