网站管理系统制作,微信小程序案例源码,管理手机网站首页,赣州若斯网络科技有限公司239. 滑动窗口最大值
给定一个数组 nums#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 进阶#xff1a; 在线性时间复杂度内解决此题#xff1f; …239. 滑动窗口最大值
给定一个数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 进阶 在线性时间复杂度内解决此题
思路-单调队列
参考https://www.programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html#%E6%80%9D%E8%B7%AF 我们需要一个队列这个队列呢放进去窗口里的元素然后随着窗口的移动队列也一进一出每次移动之后队列告诉我们里面的最大值是什么。 这个队列应该长这个样子
from collections import deque
class MyQueue:def __init__(self):self.queue deque()def pop(self, value):passdef push(self, value):passdef front(self, value):pass每次窗口移动的时候调用que.pop(滑动窗口中移除元素的数值)que.push(滑动窗口添加元素的数值)然后que.front()就返回我们要的最大值。 然后再分析一下队列里的元素一定是要排序的而且要最大值放在出队口要不然怎么知道最大值呢。 但如果把窗口里的元素都放进队列里窗口移动的时候队列需要弹出元素。 那么问题来了已经排序之后的队列 怎么能把窗口要移除的元素这个元素可不一定是最大值弹出呢。 大家此时应该陷入深思… 其实队列没有必要维护窗口里的所有元素只需要维护有可能成为窗口里最大值的元素就可以了同时保证队列里的元素数值是由大到小的。 那么这个维护元素单调递减的队列就叫做单调队列即单调递减或单调递增的队列。目前没有直接支持单调队列需要我们自己来实现一个单调队列 不要以为实现的单调队列就是 对窗口里面的数进行排序如果排序的话那和优先级队列又有什么区别了呢。 来看一下单调队列如何维护队列里的元素。 动画如下 对于窗口里的元素{2, 3, 5, 1 ,4}单调队列里只维护{5, 4} 就够了保持单调队列里单调递减此时队列出口元素就是窗口里最大元素。 此时大家应该怀疑单调队列里维护着{5, 4} 怎么配合窗口进行滑动呢 设计单调队列的时候pop和push操作要保持如下规则 pop(value)如果窗口移除的元素value等于单调队列的出口元素那么队列弹出元素否则不用任何操作 push(value)如果push的元素value大于入口元素的数值那么就将队列入口的元素弹出直到push元素的数值小于等于队列入口元素的数值为止 保持如上规则每次窗口移动的时候只要问que.front()就可以返回当前窗口的最大值。 为了更直观的感受到单调队列的工作过程以题目示例为例输入: nums [1,3,-1,-3,5,3,6,7], 和 k 3动画如下 那么我们用什么数据结构来实现这个单调队列呢 使用deque最为合适python中也有 deque用法参考https://blog.csdn.net/weixin_45666566/article/details/1084409 append、pop、extend默认是右端操作而appendleft、popleft、extendleft是左端操作。
代码
from collections import deque # 在python中也有双向队列的数据结构
# [0] 和 [-1] 是相对的class MyQueue: # 单调队列def __init__(self):self.queue deque() # 这里需要使用deque实现单调队列 直接使用list会超时# 每次pop的时候 要判断队列不为空才可以pop 另外只有当出口处的元素等于当前value的时候 才popdef pop(self, value):if self.queue and self.queue[0] value: self.queue.popleft() # list.pop()时间复杂度为O(n),这里需要使用collections.deque()# 在push的时候 如果现在进来的元素要大于队列内的元素 则队列后端的元素就要pop出去 直到现在进来的元素小于队列出口处的元素#这样就保持了队列里的数值是单调从大到小的了def push(self, value):# push前先清理一下队列内的元素# 为什么是-1呢 可以画个草图分析 见图1while self.queue and value self.queue[-1]: # deque不为空 且现在进来的元素大于队列出口元素self.queue.pop() # 那么此时出口的元素就要pop掉self.queue.append(value)#查询当前队列里的最大值 直接返回队列前端([0])也就是front就可以了。def front(self):return self.queue[0]class Solution(object):def maxSlidingWindow(self, nums, k)::type nums: List[int]:type k: int:rtype: List[int]que MyQueue()result [] # 存放结果# 前k个元素先入队列for i in range(k):que.push(nums[i])result.append(que.front()) # 前k个元素中的最大值# 后面的元素for i in range(k, len(nums)):que.pop(nums[i-k]) # 每个窗口中最前面的元素要出去que.push(nums[i]) # 后面的元素 入队列result.append(que.front()) # 将每个窗口中的最大值加入结果return result
时间复杂度: O(n)空间复杂度: O(k)
再来看一下时间复杂度使用单调队列的时间复杂度是 O(n)。 有的同学可能想了在队列中 push元素的过程中还有pop操作呢感觉不是纯粹的O(n)。 其实大家可以自己观察一下单调队列的实现nums 中的每个元素最多也就被 push_back 和 pop_back 各一次没有任何多余操作所以整体的复杂度还是 O(n)。 空间复杂度因为我们定义一个辅助队列所以是O(k)。
扩展
需要要明确的是题解中单调队列里的pop和push接口仅适用于本题哈。单调队列不是一成不变的而是不同场景不同写法总之要保证队列里单调递减或递增的原则所以叫做单调队列。 不要以为本题中的单调队列实现就是固定的写法哈。 参考https://www.programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
