1 题目
给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
2 解析
(1)方法一:大堆树
对于本题而言,初始时,我们将数组 nums 的前 k个元素放入优先队列中。每当我们向右移动窗口时,我们就可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值。
然而这个最大值可能并不在滑动窗口中,在这种情况下,这个值在数组
nums 中的位置出现在滑动窗口左边界的左侧。因此,当我们后续继续向右移动窗口时,这个值就永远不可能出现在滑动窗口中了,我们可以将其永久地从优先队列中移除。
我们不断地移除堆顶的元素,直到其确实出现在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系,我们可以在优先队列中存储二元组 (num,index),表示元素 num 在数组中的下标为 index。
注意:
python的heapq默认是小堆树,那初始化的时候,将列表元素全部取负数,就成了大堆树的思路。返回的值再取负数即可。
heapq.heapify(x):是将列表x转为小堆树
heapq.heappush(x,a),向小堆树中加入a元素
heapq.heappop(x),弹出小堆树堆顶
(2)方法二:双向递减队列
第一步:一开始,窗口中只有 1,队列中放入 1。
第二步:窗口滑动,包含了 1 和 3,3 大于 1,如果直接放入队列,队列为 1 3,不是递减队列,所以需要先将 1 移除再放入 3 。
第三步:继续滑动,窗口元素为 1 3 -1 。
第四步:滑动窗口已经有三个元素,是合格的窗口,获取它的最大值只需要获取队列的队首元素就行。
第五步:同样的,窗口不断的向右移动,每次窗口都会增加新的元素,为了让队列中的队首元素始终是当前窗口的最大值,需要把队列中所有小于新元素值的那些元素移除。
3 python 实现
(1)方法一
class Solution: # 方法一:大堆栈的方法 def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) q = [(-nums[i],i) for i in range(k)] heapq.heapify(q) ans = [-q[0][0]] for i in range(k,n): heapq.heappush(q,(-nums[i],i)) while q[0][1] <=i-k: heapq.heappop(q) ans.append(-q[0][0]) return ans
(2)方法二
class Solution: # 方法二:双端队列 def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: n = len(nums) q = collections.deque() # 先将k个元素生成单调递减队列 for i in range(k): while q and nums[i] >nums[q[-1]]: q.pop() q.append(i) # 首个窗口的最大元素进列表 res = [nums[q[0]]] # 再依次入单调递减队列 for i in range(k,n): while q and nums[i]>nums[q[-1]]: q.pop() q.append(i) # 当队列长度超过k个,就弹出队首 while q[0]<=i-k: q.popleft() res.append(nums[q[0]]) return res