代码随想录算法训练营第十三天|239. 滑动窗口最大值、347. 前 K 个高频元素

【参考链接】

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.这道题目主要涉及到如下三块内容：

1. 要统计元素出现频率
2. 对频率排序
3. 找出前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