滑動(dòng)窗口最大值

題解：

使用單調(diào)隊(duì)列，放進(jìn)去窗口里的元素，隨著窗口的移動(dòng)，隊(duì)列也一進(jìn)一出，每次移動(dòng)之后，就會(huì)得到窗口的最大值是什么。隊(duì)列里的數(shù)據(jù)一定是要排序的，不然不知道最大值，但如果吧窗口里的元素都放進(jìn)隊(duì)列里，窗口移動(dòng)的時(shí)候，隊(duì)列需要彈出元素，其實(shí)隊(duì)列沒有必要維護(hù)窗口里的所有元素，只需要維護(hù)有可能成為窗口里最大值的元素就可以了，同時(shí)保證隊(duì)列里的元素?cái)?shù)值是有大到小的。采用單調(diào)遞減隊(duì)列

設(shè)計(jì)打你到隊(duì)列的時(shí)候：

pop（value）：如果窗口移除元素的value等于單調(diào)隊(duì)列的出口元素，那么隊(duì)列彈出元素，否則不用任何操作

push(value)：如果push的元素value大于入口的元素，那么將隊(duì)列入口的元素彈出，直到push元素的數(shù)值小于等于隊(duì)列入口元素的數(shù)值為止

front，返回的是隊(duì)列窗口最大值

代碼：

前K個(gè)高頻元素

題解：

涉及到三個(gè)內(nèi)容：

1.統(tǒng)計(jì)元素出現(xiàn)的頻率

2.對(duì)頻率排序

3.找出前k個(gè)高頻元素

使用優(yōu)先隊(duì)列，也就是堆，使用大頂堆還是小頂堆。

大頂堆：定義個(gè)大小為k的大頂堆，在每次移動(dòng)更新大頂堆的時(shí)候，每次彈出都把最大的元素彈出，如何保留下來前k個(gè)高頻元素？而且使用大頂堆就要吧所有元素進(jìn)行排序

小頂堆：統(tǒng)計(jì)最大前k個(gè)元素，只有小頂堆每次將最小的元素彈出，最后小頂堆里積累的才是前k個(gè)最大元素

因此使用小頂堆

代碼：