239. 滑动窗口最大值
【注意】
1.使用单调队列的经典题目。
2.大顶堆每次只能弹出最大值，无法移除其他数值，造成大顶堆维护的不是滑动窗口里面的数值了。所以不能用大顶堆。
3.需要一个队列，放进去窗口里的元素，然后随着窗口的移动，队列也一进一出，每次移动之后，队列告诉我们里面的最大值是什么。
4.要最大值放在出队口。
5.队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
6.使用单调队列的时间复杂度是 O(n)，空间复杂度: O(k)。
【代码】
1.pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。
2.push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。
保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。
3.deque是可以两边扩展的，而且deque里元素并不是严格的连续分布的。
1 from collections import deque 2 3 class MyQueue: 4 #单调队列（从大到小） 5 def __init__(self): 6 #这里需要使用deque实现单调队列，直接使用list会超时 7 self.queue = deque() 8 9 #每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。 10 #同时pop之前判断队列当前是否为空。 11 def pop(self, value): 12 if self.queue and value == self.queue[0]: #队口 13 self.queue.popleft() 14 #list.pop()时间复杂度为O(n),这里需要使用collections.deque() 15 16 #如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。 17 #这样就保持了队列里的数值是单调从大到小的了。 18 def push(self,value): 19 while self.queue and value > self.queue[-1]: 20 #在push的时候就把小于value值卷走 21 self.queue.pop() #调用的queue自己的pop方法 22 self.queue.append(value) 23 24 #查询当前队列里的最大值 直接返回队列前端也就是front就可以了。 25 def front(self): 26 return self.queue[0] 27 28 class Solution(object): 29 def maxSlidingWindow(self, nums, k): 30 """ 31 :type nums: List[int] 32 :type k: int 33 :rtype: List[int] 34 """ 35 que = MyQueue() 36 result = [] 37 for i in range(k): 38 #先将前k的元素放进队列 39 que.push(nums[i]) 40 #result 记录前k的元素的最大值 41 result.append(que.front()) 42 #将剩余的元素放入que中 43 for i in range(k, len(nums)): 44 #滑动窗口移除最前面元素 45 que.pop(nums[i-k]) 46 #滑动窗口前加入最后面的元素 47 que.push(nums[i]) 48 #记录对应的最大值 49 result.append(que.front()) 50 51 return result
347. 前 K 个高频元素
【注意】
1.这道题目主要涉及到如下三块内容：
- 要统计元素出现频率
- 对频率排序
- 找出前K个高频元素
2.对频率进行排序，使用一种容器适配器就是优先级队列。
3.优先级队列：其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。
4.堆是一棵完全二叉树，树中每个结点的值都不小于（或不大于）其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆，小于等于左右孩子就是小顶堆。
5.要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。
6.时间复杂度: O(nlogk)，空间复杂度: O(n)。
【代码】
1.for i in range(k-1, -1, -1):range(start, end, step), 其中start为闭，end为开，正数为正方向（向后遍历）步长。range(len-1,-1,-1):代表起点是数组最后一个元素，终点是数组第一个元素，每次往前遍历一个元素。
2.heapq:【参考链接】
1 import heapq #堆队列 2 3 class Solution(object): 4 def topKFrequent(self, nums, k): 5 """ 6 :type nums: List[int] 7 :type k: int 8 :rtype: List[int] 9 """ 10 #要统计元素出现频率 11 #nums[i]:对应出现的次数 12 map_ = {} #字典实现map 13 14 for i in range(len(nums)): 15 # 如果指定键不存在，默认按照get(key,val)中val的值赋予该键 16 map_[nums[i]] = map_.get(nums[i], 0) + 1 #累加 17 18 #对频率排序 19 #定义一个小顶堆，大小为k 20 pri_que = [] #小顶堆 21 22 #用固定大小为k的小顶堆，扫描所有频率的数值 23 for key, freq in map_.items(): 24 # 将（freq，key）的元组加入heap中，保持堆的不变性。 25 heapq.heappush(pri_que,(freq,key)) 26 #如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k 27 if len(pri_que) > k: 28 # 弹出并返回 heap 的最小的元素，保持堆的不变性。如果堆为空，抛出IndexError 29 heapq.heappop(pri_que) 30 31 32 #找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组 33 result = [0] * k 34 for i in range(k-1, -1, -1): 35 # 元组内第二个值为key 36 result[i] = heapq.heappop(pri_que)[1] 37 38 return result