滑动窗口最大值
Sliding Window Maximum
本机进度仅保存在当前浏览器
题目描述
给你一个整数数组 nums 和滑动窗口大小 k，窗口从数组最左侧滑到最右侧，返回每个窗口中的最大值组成的数组。
示例：nums = [1, 3, -1, -3, 5, 3, 6, 7]，k = 3，输出 [3, 3, 5, 5, 6, 7]。
解题思路
- 暴力每窗取最大是 O(n·k)；维护一个「值单调递减」的双端队列可把均摊代价降到 O(1)。
- 队列存下标，对应值从头到尾递减，队头永远是当前窗口最大值。
- 新元素入队前，把队尾所有比它小的元素弹出——它们不可能再成为之后任何窗口的最大值。
- 队头下标滑出窗口范围（<= i - k）时从头部弹出；窗口形成后（i >= k-1）每步记录队头值。
参考实现
查看参考实现Python · 建议先自行作答
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # 存下标，对应值单调递减
res = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
if dq[0] <= i - k:
dq.popleft()
if i >= k - 1:
res.append(nums[dq[0]])
return res