代码随想录(11)栈和队列(3)

 ZR_yst     2023-11-21     351     0   

欢迎来到银盒子的世界~

图片.png




对了,我就记得不是用优先级队列(大/小顶堆),而是单调队列(自己实现),然后确保是一个单减的队列,这样每次的最大值就在队首取,然后移动窗口时判断是不是最大的元素移出去了,否则就不用管。

(1)选择双端队列实现,然后push的时候判断是不是比队尾的大,是的话就pop直到满足单减

(2)pop的时候判断是不是队首的,是的话就出队,否则不用管(因为就没在队列里)

(3)取最大值的话就返回队首元素

(4)运用的时候就是前k个入队,后面的一出一入,返回最大值,最后返回这个list

图片.png



图片.png


嗷嗷,好吧,是这样的,要用小顶堆,然后限制大小为k,超出就pop,这样最后剩下的就是前k大的数,最后记得反一下

'''

Heapq库

这个模块提供了堆队列算法的实现,也称为优先队列算法

heapq.heappush(heap, item)

item 的值加入 heap 中,保持堆的不变性。

heapq.heappop(heap)

弹出并返回 heap 的最小的元素,保持堆的不变性。如果堆为空,抛出 IndexError 。使用 heap[0] ,可以只访问最小的元素而不弹出它。

heapq.heapify(x)

将list x 转换成堆,原地,线性时间内。

heapq.heapreplace(heap, item)

弹出并返回 heap 中最小的一项,同时推入新的 item。 堆的大小不变。 如果堆为空则引发 IndexError

这个单步骤操作比 heappop()heappush() 更高效,并且在使用固定大小的堆时更为适宜。 pop/push 组合总是会从堆中返回一个元素并将其替换为 item

返回的值可能会比添加的 item 更大。 如果不希望如此,可考虑改用 heappushpop()。 它的 push/pop 组合会返回两个值中较小的一个,将较大的值留在堆中

'''



图片.png

发表评论