今日内容：
- 239. 滑动窗口最大值
- 347.前 K 个高频元素
- 总结
239. 滑动窗口最大值 （一刷至少需要理解思路）
class Myqueue(object):def __init__(self):self.queue = deque()#保留队列最大的元素在队列里面，其他都pop掉def push(self,value):while len(self.queue)!=0 and value > self.queue[-1]:self.queue.pop()self.queue.append(value)def pop(self,value):if len(self.queue)!=0 and self.queue[0] == value:self.queue.popleft()#获取即将出队的元素def getMax(self):return self.queue[0]class Solution(object):def maxSlidingWindow(self, nums, k):que = Myqueue()result = []for i in range(k):que.push(nums[i])result.append(que.getMax())for i in range(k,len(nums)):que.pop(nums[i-k])que.push(nums[i])result.append(que.getMax())return result重点：
如何求窗口的最大值：使用队列。这个队列需要实现三个功能:pop(),push(),getmax()。
不能使用堆，这是因为经过排序后，不知道pop出来的元素是什么。
保存的一直都是三个数中最大的数！！
题目链接/文章讲解/视频讲解：代码随想录
二刷：
未ac
def push(self,value):while len(self.que)!=0 and value > self.que[-1]:self.que.pop()self.que.append(value)我写的是
def push(self,value):while len(self.que)!=0 and value > self.que[0]:self.que.popleft()self.que.append(value)就是入口处会不会比他小，小的话pop出去。因为可能第一个数（出口处）跟他一样大。那他不就不push出去了，所以得从入口处开始一个一个pop出去
pop()的话是stack中的用法，pop出去的是入口处的元素
popleft()是出口处的元素
三刷
var maxSlidingWindow = function(nums, k) {class MyQueue{constructor(){this.que = []}myPush(value){let back = this.que[this.que.length-1]while(back!==undefined && back<value){this.que.pop()back = this.que[this.que.length-1]}this.que.push(value)}myPop(value){if(this.que.length && value === this.getMaxValue()){// 弹出第一个元素this.que.shift()}}getMaxValue(){return this.que[0]}}let myque = new MyQueue()for(let i = 0;i<k;i++){myque.myPush(nums[i])}let result = []result.push(myque.getMaxValue())let slow = 0let fast = kwhile(slow < fast && fast< nums.length){myque.myPop(nums[slow])myque.myPush(nums[fast])result.push(myque.getMaxValue())slow ++fast ++}return result
};347.前 K 个高频元素
class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""import heapqhashmap = {}result = []#使用最大堆minheap = []heapq.heapify(minheap)#将nums存入哈希表中，Python中自带的堆heapq,不支持自定义的比较函数,但是可以自己创建自定义函数for num in nums:hashmap[num] = hashmap.get(num,0)+1#遍历hashmapfor key,fre in hashmap.items():heapq.heappush(minheap,(fre,key))if len(minheap) > k:heapq.heappop(minheap)while len(minheap)!=0:temp = heapq.heappop(minheap)result.append(temp[1])return result重点：
- 如何求频率：map：key 是num，value是count
- 如何排序：使用大小堆顶，多适合求前k个高频或者低频的元素
- 如何使用python自带的堆的比较函数
整体比较简单。就是不知道如何比较这个频率的值
比较函数：__lt__对应<，当对象之间用<比较大小的时候，就会调用__lt__方法。同样的>会调用__gt__方法，在只重写了__lt__方法的时候，__gt__会对__lt__结果取反。但是当比较相等的时候，二者的结果是相等的。
class P():def __init__(self,a,b):self.a = aself.b = bdef __lt__(self, other):if self.b<other.b:return Trueelse:return False
————————————————
版权声明：本文为CSDN博主「七月听雪」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_23262411/article/details/104854417题目链接/文章讲解/视频讲解：代码随想录
二刷：
未ac
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:#统计出现频率,key为num，get(key)为频率hashmap = {}for num in nums:hashmap[num] = hashmap.get(num,0)+1#对频率进行排序import heapqminheap = []heapq.heapify(minheap)for key,fre in hashmap.items():heapq.heappush(minheap,[fre,key])#如果超过k个，就pop出来if len(minheap)>k:heapq.heappop(minheap)print(minheap)result = []#循环遍历一下，将key指加入到结果集中for heap in minheap:result.append(heap[1])return result三刷
// 实现一个小顶堆
class Heap {constructor() {this.heap = [];}add(value) {this.heap.push(value);// 获取当前加入值的下标this.heapUp(this.heap.length - 1);}poll() {// 如果 heap 中没有元素if (this.heap.length === 0) {return null;}// 如果 heap 中有一个元素if (this.heap.length === 1) {return this.heap.pop();}// 如果 heap 中有两个及以上元素const item = this.heap[0];this.heap[0] = this.heap.pop();this.heapify(0);return item;}// 将一个元素移动到堆中正确的位置heapUp(index) {// 我们需要计算在父节点的位置const parentIndex = Math.floor((index - 1) / 2);if (parentIndex >=0 && parentIndex < this.heap.length && this.heap[parentIndex][1] > this.heap[index][1]) {this.swap(parentIndex, index);this.heapUp(parentIndex);}}// 需要判断左右孩子，是否比当前元素小heapify(index) {let leftIndex = index * 2 + 1;let rightIndex = index * 2 + 2;let curIndex = index;if (leftIndex < this.heap.length && this.heap[leftIndex][1] < this.heap[curIndex][1]) {curIndex = leftIndex;}if (rightIndex < this.heap.length && this.heap[rightIndex][1] < this.heap[curIndex][1]) {curIndex = rightIndex;}if (curIndex !== index) {this.swap(index, curIndex);this.heapify(curIndex);}}swap(index1, index2) {[this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];}
}
var topKFrequent = function(nums, k) {//将频率存入map中let map = new Map()for (let i = 0; i < nums.length; i++) {map.set(nums[i], (map.get(nums[i]) || 0) + 1)}//建立堆结构let heap = new Heap();for (let [num, count] of map) {heap.add([num, count]);console.log(heap)if (heap.heap.length > k) {heap.poll();}}
}// 将堆中的元素输出
var topKFrequent = function(nums, k) {//将频率存入map中let map = new Map();for (let i = 0; i < nums.length; i++) {map.set(nums[i], (map.get(nums[i]) || 0) + 1);}//建立堆结构let heap = new Heap();for (let [num, count] of map) {heap.add([num, count]);if (heap.heap.length > k) {heap.poll();}}// 取出堆中的元素const result = [];while (heap.heap.length) {result.unshift(heap.poll()[0]);}return result;
};unshift() 方法可向数组的开头添加一个或更多元素，并返回新的长度。
注意： 该方法将改变数组的数目。
