239 滑动窗口的最大值
代码语言：javascript复制class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
from collections import deque
queue = deque()
res = []
for i in range(len(nums)):
if i < k - 1:
# 先初始化窗口里面的值
queue.append(nums[i])
else:
# 窗口开始移动
queue.append(nums[i])
res.append(max(queue))
queue.popleft()
return res
尽管我们已经使用了双向队列，但是还是超时了。下面是修改后的代码：
代码语言：javascript复制from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
queue = deque()
res = []
# 我们存储的是索引
for i in range(len(nums)):
# 如果i >= k且最大值正好位于窗口左端，则将其移除
if i >= k and i - k == queue[0]:
queue.popleft()
# 如果当前值比queue里面最后的值要大，则删除queue最后的值
while queue and nums[i] >= nums[queue[-1]]:
queue.pop()
queue.append(i)
if i >= k-1:
# queue中的首位保证是最大值
res.append(nums[queue[0]])
return res举个例子： res = s.maxSlidingWindow([1,3,-1,-3,5,3,6,7],3) i: 0 nums[i]: 1 queue: [1] i: 1 nums[i]: 3 queue: [3] i: 2 nums[i]: -1 queue: [3, -1] res: [3] i: 3 nums[i]: -3 queue: [3, -1, -3] res: [3, 3] i: 4 nums[i]: 5 queue: [5] res: [3, 3, 5] i: 5 nums[i]: 3 queue: [5, 3] res: [3, 3, 5, 5] i: 6 nums[i]: 6 queue: [6] res: [3, 3, 5, 5, 6] i: 7 nums[i]: 7 queue: [7] res: [3, 3, 5, 5, 6, 7]
