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
