239. 滑动窗口最大值 （一刷至少需要理解思路）
题目链接：
239. 滑动窗口最大值 - 力扣（Leetcode）
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
第一次刷到困难题比较激动，确实能写出来，算例能过一部分，但是大规模会超出时间，看了视频讲解才明白要用单调队列。觉得刷题越来越有意思了，希望代码能力能够越来越强。
收获的点：
1）自己构建单调队列，保证单调在于每一次加进来的元素之前都会把前面比他小的元素删掉；
2）最后结果部分调用顺序的逻辑。
from collections import deque
class MyQueue: #单调队列（从大到小
def __init__(self):
self.queue = deque() #这里需要使用deque实现单调队列，直接使用list会超时
#每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
#同时pop之前判断队列当前是否为空。
def pop(self, value):
if self.queue and value == self.queue[0]:
self.queue.popleft()#list.pop()时间复杂度为O(n),这里需要使用collections.deque()
#如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
#这样就保持了队列里的数值是单调从大到小的了。
def push(self, value):
while self.queue and value > self.queue[-1]:
self.queue.pop()
self.queue.append(value)
#查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
def front(self):
return self.queue[0]
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
que = MyQueue()
result = []
for i in range(k): #先将前k的元素放进队列
que.push(nums[i])
result.append(que.front()) #result 记录前k的元素的最大值
for i in range(k, len(nums)):
que.pop(nums[i - k]) #滑动窗口移除最前面元素
que.push(nums[i]) #滑动窗口前加入最后面的元素
result.append(que.front()) #记录对应的最大值
return result
347.前 K 个高频元素
题目链接：
347. 前 K 个高频元素 - 力扣（Leetcode）
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
收获的点：
Python中heapq模块
heapq模块给我的感觉是定义了一个列表，这个列表能够实现一些特定的功能，比如
heappush(heap,item)将push进去的item输出后是排好序的；
import heapq
a = [] #创建一个空堆
heapq.heappush(a,18)
heapq.heappush(a,1)
heapq.heappush(a,20)
heapq.heappush(a,10)
heapq.heappush(a,5)
heapq.heappush(a,200)
print(a)
输出
[1, 5, 20, 18, 10, 200]
heapq里面没有直接提供建立大根堆的方法，可以采取如下方法：每次push时给元素加一个负号（即取相反数），此时最小值变最大值，反之亦然，那么实际上的最大值就可以处于堆顶了，返回时再取负即可。
a = []
for i in [1, 5, 20, 18, 10, 200]:
heapq.heappush(a,-i)
print(list(map(lambda x:-x,a)))
#输出
[200, 18, 20, 1, 10, 5]
heapify(heap)传入一个列表heap能够将他变成小顶堆；
a = [1, 5, 20, 18, 10, 200]
heapq.heapify(a)
print(a)
heapq.heappop()是从堆中弹出并返回最小的值；
>>> a=[3,6,1]
>>> heapify(a) #将a变成堆之后，可以对其操作
>>> heappop(a)
1
>>> b=[4,2,5] #b不是堆，如果对其进行操作，显示结果如下
>>> heappop(b) #按照顺序，删除第一个数值并返回,不会从中挑选出最小的
4
>>> heapify(b) #变成堆之后，再操作
>>> heappop(b)
2
heapq.heappushpop()是heappush和haeppop的结合，同时完成两者的功能，先进行heappush()，再进行heappop()；
>>>h = [1, 2, 9, 5]
>>> heappop(h)
1
>>> heappushpop(h,4) #增加4同时删除最小值2并返回该最小值，与下列操作等同：
2
>>> h
[4, 5, 9]
heapq.heapreplace()与heapq.heappushpop()相反，先进行heappop()，再进行heappush()；
>>> a=[]
>>> heapreplace(a,3) #如果list空，则报错
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: index out of range
>>> heappush(a,3)
>>> a
[3]
>>> heapreplace(a,2) #先执行删除（heappop(a)->3),再执行加入（heappush(a,2))
3
>>> a
[2]
>>> heappush(a,5)
>>> heappush(a,9)
>>> heappush(a,4)
>>> a
[2, 4, 9, 5]
>>> heapreplace(a,6) #先从堆a中找出最小值并返回，然后加入6
2
>>> a
[4, 5, 9, 6]
>>> heapreplace(a,1) #1是后来加入的，在1加入之前，a中的最小值是4
4
>>> a
[1, 5, 9, 6]
完整代码：
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
CollectionMap = Counter(nums)
heap = [(val,key) for key,val in CollectionMap.items()]
return [item[1] for item in heapq.nlargest(k,heap)]
#时间复杂度：O(nlogk)
#空间复杂度：O(n)
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
#要统计元素出现频率
map_ = {} #nums[i]:对应出现的次数
for i in range(len(nums)):
map_[nums[i]] = map_.get(nums[i], 0) + 1
#对频率排序
#定义一个小顶堆，大小为k
pri_que = [] #小顶堆
#用固定大小为k的小顶堆，扫描所有频率的数值
for key, freq in map_.items():
heapq.heappush(pri_que, (freq, key))
if len(pri_que) > k: #如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
heapq.heappop(pri_que)
#找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
result = [0] * k
for i in range(k-1, -1, -1):
result[i] = heapq.heappop(pri_que)[1]
return result
