239. 滑動窗口最大值

單調隊列

滑動窗口中的隊列一直保持出口大，入口小的順序。（圖：代碼隨想錄）

1、每次有新的元素進入（也就是滑動窗口移動后），都需要先和入口的元素比較大小，如果大，就從隊尾pop出之前的元素（雙向隊列的特性），如果小，則保留。

2、每次需要pop隊列頭部的元素，需要先和當前隊列的頭部元素比較，只pop滑動窗口即將舍棄的值。

from collections import dequeclass MyQueue:"""雙向隊列dequeue始終保持隊列頭部pop()為最大值，尾部push()為最小值pop<-- [0] [1] [-1] <--pushmax mid min"""def __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天完結🎉