题目
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧挪动到数组的最右侧。你只能够看到在滑动窗口内的 k 个数字。滑动窗口每次只向右挪动一位。
返回 滑动窗口中的最大值。
输出:nums = [1,3,-1,-3,5,3,6,7], k = 3
输入:[3,3,5,5,6,7]
解释:滑动窗口的地位 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
输出:nums = [1], k = 1
输入:[1]
思路
双端队列
用一个双端队列,模仿窗口
遍历数组:
- 队列为空,以后元素间接退出队列中
- 队列不为空,以后元素 < 队尾元素,以后元素退出队列中;以后元素 >= 队尾元素,弹出队尾元素,以后元素退出队列中。这样保障队头元素,永远是以后窗口的最大值。
- 队头元素超出了窗口范畴,弹出队头元素
队列中退出的并不是元素的值,而是元素在数组中的下标,这么做是为了通过下标判断队头元素是否超出了窗口范畴
import collections
def maxSlidingWindow(nums, k):
n = len(nums)
# 定义一个双端队列,模仿窗口
q = collections.deque()
# 数组 ans 保留后果
ans = []
# 第一个窗口没有齐全进入数组中,独自解决
#【】[1,2,3...]【[1】,2,3...]【[1,2】,3...] [【1,2,3】,...]
for i in range(k):
# 以后 >= 队尾,删除队尾,退出以后
while q and nums[i]>=nums[q[-1]]:
q.pop()
q.append(i)
# 保留第一个窗口的最大值
ans.append(nums[q[0]])
# 第二个窗口开始,齐全在数组中挪动了
for i in range(k,n):
# 随着窗口挪动,判断队头是否还在窗口范畴中,不在就删除
if q[0]<=i-k:
q.popleft()
# 以后 >= 队尾,删除队尾,退出以后
while q and nums[i]>=nums[q[-1]]:
q.pop()
q.append(i)
# 以后队头是以后窗口的最大值,保留最大值到 ans
ans.append(nums[q[0]])
return ans
- 为什么要判断队头元素在不在窗口范畴,窗口每次挪动,队头必定就不在窗口范畴了,间接删除队头不就好了?
队头是以后窗口的最大元素,不是最右边元素,所以要判断随着窗口个挪动,队头元素还在不在窗口范畴中。 -
为什么以后元素 < 队尾元素,以后元素还要退出队列。不退出可不可以,只有放弃队头是以后窗口最大元素不就行了?
[【5,3,2】,1],假如以后窗口队头是 5,前面的 3,2 都小于 5,如果 3、2 不退出队列中,遍历到 1 的时候,5 超过窗口范畴被删除,此时队列就是空的,那 1 就成了以后窗口的最大值,显然是谬误的。退出 正确 不退出 谬误【5,3,2】,1【5】,3,2,1 5,【3,2,1】5,3,2,【1】