团购网站为什么做不走,浙江职业能力建设网,足彩彩票网站建设,做婚庆的网站有哪些239. 滑动窗口最大值
单调队列
滑动窗口中的队列一直保持出口大#xff0c;入口小的顺序。#xff08;图#xff1a;代码随想录#xff09; 1、每次有新的元素进入#xff08;也就是滑动窗口移动后#xff09;#xff0c;都需要先和入口的元素比较大小#xff0c;如果…239. 滑动窗口最大值
单调队列
滑动窗口中的队列一直保持出口大入口小的顺序。图代码随想录 1、每次有新的元素进入也就是滑动窗口移动后都需要先和入口的元素比较大小如果大就从队尾pop出之前的元素双向队列的特性如果小则保留。
2、每次需要pop队列头部的元素需要先和当前队列的头部元素比较只pop滑动窗口即将舍弃的值。
from collections import dequeclass MyQueue:双向队列dequeue始终保持队列头部pop()为最大值尾部push()为最小值pop-- [0] [1] [-1] --pushmax mid mindef __init__(self):self.queue deque()def pop(self, value):# 如果队列非空而且需要pop的值恰好就是队头的数值if self.queue and value self.queue[0]:self.queue.popleft()def push(self, value):# 如果队列非空而且需要push进入的值比队尾的值都大那么队尾就一直pop出去while self.queue and value self.queue[-1]:self.queue.pop()self.queue.append(value)def getMax(self):# 始终保持头部是最大值返回队列头部就是最大值return self.queue[0]class Solution(object):def maxSlidingWindow(self, nums, k)::type nums: List[int]:type k: int:rtype: List[int]queue MyQueue()ans []# 先储存前k个数值保证队列非空for i in range(k):queue.push(nums[i])ans.append(queue.getMax())# 然后遍历nums数组for i in range(k, len(nums)):queue.pop(nums[i - k])queue.push(nums[i])ans.append(queue.getMax())return ans
347. 前 K 个高频元素
大顶堆根节点是最大值先pop的是最大值
小顶堆根节点是最小值先pop的是最小值。
所以只需要按照出现频率排序放入小顶堆然后pop直到还剩k个元素再按照倒序输出即可。
优先级队列法
1、首先遍历数组建立map键值对
2、建立小顶堆按照从大到小的顺序放入键值对当队列的长度大于k的时候开始从最小值节点pop元素留下k个最大值
3、倒序输出最大值对应的key即可。
class Solution(object):def topKFrequent(self, nums, k)::type nums: List[int]:type k: int:rtype: List[int]# 获取键值对map_freq {} # (key, value) (a, 4), (b, 3) ...for item in nums:map_freq[item] map_freq.get(item, 0) 1 # 注意get写法# 构造小顶堆prime_que [] # 创建优先级队列这里是小顶堆heapq用法heapq.heappush()是往堆中添加新值heapq.heappop()是从堆的根节点弹出值大顶堆弹出最大值小顶堆弹出最小值for key, value in map_freq.items():heapq.heappush(prime_que, (value, key)) # 先入的是最大值if len(prime_que) k:heapq.heappop(prime_que)res [0] * k# 倒序输出for i in range(k-1, -1, -1):res[i] heapq.heappop(prime_que)[1]return res
注意构造小顶堆的方式heapq heapq用法 heapq.heappush()是往堆中添加新值 heapq.heappop()是从堆的根节点弹出值大顶堆弹出最大值小顶堆弹出最小值 第13天完结
