每日leetcode——239. 滑动窗口最大值
题目
【每日leetcode——239. 滑动窗口最大值】给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
输入:nums = [1,3,-1,-3,5,3,6,7], k = 3
输出:[3,3,5,5,6,7]
解释:
滑动窗口的位置最大值
--------------------
[13-1] -353673
1 [3-1-3] 53673
13 [-1-35] 3675
13-1 [-353] 675
13-1-3 [536] 76
13-1-35 [367]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就成了当前窗口的最大值,显然是错误的。
加入 正确不加入 错误 # 遍历到2 【5,3,2】,1【5】,3,2,1 # 遍历到1 5,【3,2,1】5,3,2,【1】
推荐阅读
- 『德不孤』Pytest框架|『德不孤』Pytest框架 — 15、Pytest参数化
- 每日leetcode——232. 用栈实现队列
- LittleTips——显示当前程序快捷键列表
- Element|Element Plus 源码分析——构建与代码风格
- python|数字图像基本操作——图像采样、量化、算术运算、点运算实验结果及分析
- —OpenCV|OpenCV-Python——第7章(图像的基本运算)
- 机器学习 —— 类不平衡问题与SMOTE过采样算法
- OpenCV|OpenCV图像处理和应用—色彩空间与几何变换(一)
- OpenCV从入门到精通|OpenCV中的图像处理 —— 改变颜色空间+图像几何变换
- OpenCV从入门到精通|OpenCV的核心操作 —— 图像的基本操作+图像上的算术运算