239. 滑動(dòng)窗口最大值 （一刷至少需要理解思路）

題目鏈接：

239. 滑動(dòng)窗口最大值 - 力扣（Leetcode）
給你一個(gè)整數(shù)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。
返回 滑動(dòng)窗口中的最大值 。

第一次刷到困難題比較激動(dòng)，確實(shí)能寫(xiě)出來(lái)，算例能過(guò)一部分，但是大規(guī)模會(huì)超出時(shí)間，看了視頻講解才明白要用單調(diào)隊(duì)列。覺(jué)得刷題越來(lái)越有意思了，希望代碼能力能夠越來(lái)越強(qiáng)。

收獲的點(diǎn)：

1）自己構(gòu)建單調(diào)隊(duì)列，保證單調(diào)在于每一次加進(jìn)來(lái)的元素之前都會(huì)把前面比他小的元素刪掉；
2）最后結(jié)果部分調(diào)用順序的邏輯。

from collections import deque
class MyQueue: #單調(diào)隊(duì)列（從大到小
    def __init__(self):
        self.queue = deque() #這里需要使用deque實(shí)現(xiàn)單調(diào)隊(duì)列，直接使用list會(huì)超時(shí)
    #每次彈出的時(shí)候，比較當(dāng)前要彈出的數(shù)值是否等于隊(duì)列出口元素的數(shù)值，如果相等則彈出。
    #同時(shí)pop之前判斷隊(duì)列當(dāng)前是否為空。
    def pop(self, value):
        if self.queue and value == self.queue[0]:
            self.queue.popleft()#list.pop()時(shí)間復(fù)雜度為O(n),這里需要使用collections.deque()            
    #如果push的數(shù)值大于入口元素的數(shù)值，那么就將隊(duì)列后端的數(shù)值彈出，直到push的數(shù)值小于等于隊(duì)列入口元素的數(shù)值為止。
    #這樣就保持了隊(duì)列里的數(shù)值是單調(diào)從大到小的了。
    def push(self, value):
        while self.queue and value > self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)        
    #查詢當(dāng)前隊(duì)列里的最大值 直接返回隊(duì)列前端也就是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的元素放進(jìn)隊(duì)列
            que.push(nums[i])
        result.append(que.front()) #result 記錄前k的元素的最大值
        for i in range(k, len(nums)):
            que.pop(nums[i - k]) #滑動(dòng)窗口移除最前面元素
            que.push(nums[i]) #滑動(dòng)窗口前加入最后面的元素
            result.append(que.front()) #記錄對(duì)應(yīng)的最大值
        return result

347.前 K 個(gè)高頻元素

題目鏈接：

347. 前 K 個(gè)高頻元素 - 力扣（Leetcode）
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，請(qǐng)你返回其中出現(xiàn)頻率前 k 高的元素。你可以按 任意順序 返回答案。

收獲的點(diǎn)：

Python中heapq模塊
heapq模塊給我的感覺(jué)是定義了一個(gè)列表，這個(gè)列表能夠?qū)崿F(xiàn)一些特定的功能，比如
heappush(heap,item)將push進(jìn)去的item輸出后是排好序的；

import heapq
a = []   #創(chuàng)建一個(gè)空堆
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里面沒(méi)有直接提供建立大根堆的方法，可以采取如下方法：每次push時(shí)給元素加一個(gè)負(fù)號(hào)（即取相反數(shù)），此時(shí)最小值變最大值，反之亦然，那么實(shí)際上的最大值就可以處于堆頂了，返回時(shí)再取負(fù)即可。

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)傳入一個(gè)列表heap能夠?qū)⑺兂尚№敹眩?/p>

a = [1, 5, 20, 18, 10, 200]
heapq.heapify(a)
print(a)

heapq.heappop()是從堆中彈出并返回最小的值；

>>> a=[3,6,1]
>>> heapify(a)                  #將a變成堆之后，可以對(duì)其操作
>>> heappop(a)
1
>>> b=[4,2,5]                   #b不是堆，如果對(duì)其進(jìn)行操作，顯示結(jié)果如下
>>> heappop(b)                  #按照順序，刪除第一個(gè)數(shù)值并返回,不會(huì)從中挑選出最小的
4
>>> heapify(b)                  #變成堆之后，再操作
>>> heappop(b)
2

heapq.heappushpop()是heappush和haeppop的結(jié)合，同時(shí)完成兩者的功能，先進(jìn)行heappush()，再進(jìn)行heappop()；

>>>h =  [1, 2, 9, 5]
>>> heappop(h)
1
>>> heappushpop(h,4)            #增加4同時(shí)刪除最小值2并返回該最小值，與下列操作等同：
2                              
>>> h
[4, 5, 9]

heapq.heapreplace()與heapq.heappushpop()相反，先進(jìn)行heappop()，再進(jìn)行heappush()；

>>> a=[]
>>> heapreplace(a,3)            #如果list空，則報(bào)錯(cuò)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: index out of range
>>> heappush(a,3)
>>> a
[3]
>>> heapreplace(a,2)            #先執(zhí)行刪除（heappop(a)->3),再執(zhí)行加入（heappush(a,2))
3
>>> a
[2]
>>> heappush(a,5)  
>>> heappush(a,9)
>>> heappush(a,4)
>>> a
[2, 4, 9, 5]
>>> heapreplace(a,6)            #先從堆a(bǔ)中找出最小值并返回，然后加入6
2
>>> a
[4, 5, 9, 6]
>>> heapreplace(a,1)            #1是后來(lái)加入的，在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)] 

#時(shí)間復(fù)雜度：O(nlogk)
#空間復(fù)雜度：O(n)
import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        #要統(tǒng)計(jì)元素出現(xiàn)頻率
        map_ = {} #nums[i]:對(duì)應(yīng)出現(xiàn)的次數(shù)
        for i in range(len(nums)):
            map_[nums[i]] = map_.get(nums[i], 0) + 1
        
        #對(duì)頻率排序
        #定義一個(gè)小頂堆，大小為k
        pri_que = [] #小頂堆
        
        #用固定大小為k的小頂堆，掃描所有頻率的數(shù)值
        for key, freq in map_.items():
            heapq.heappush(pri_que, (freq, key))
            if len(pri_que) > k: #如果堆的大小大于了K，則隊(duì)列彈出，保證堆的大小一直為k
                heapq.heappop(pri_que)
        
        #找出前K個(gè)高頻元素，因?yàn)樾№敹严葟棾龅氖亲钚〉?，所以倒序?lái)輸出到數(shù)組
        result = [0] * k
        for i in range(k-1, -1, -1):
            result[i] = heapq.heappop(pri_que)[1]
        return result