25期代码随想录算法训练营第十三天

算法训练营第十三天"/>

25期代码随想录算法训练营第十三天

目录

• 239. 滑动窗口最大值
• 347.前 K 个高频元素
• • 方法一
  • 方法二

239. 滑动窗口最大值

链接

窗口 — 维持一个单调递增队列

为什么要使用队列？

• 在窗口移动的时候，方便把不属于窗口的最大值剔除。（当窗口移动之后）

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:q = deque() # store indexres = []l = r = 0while r < len(nums):# push# make sure that it's a mono increasing queuewhile q and nums[q[-1]] < nums[r]:q.pop()q.append(r)# pop element # since it's not in the window anymoreif l > q[0]:q.popleft()# append the max num in the window to res# only when a window is formed can we move the l pointerif (r + 1) >= k:res.append(nums[q[0]])l += 1r += 1return res

347.前 K 个高频元素

链接

方法一

Counter得到频率表，反转频率表，再进行heapify。
heappop前k个元素，即为前K个高频元素。

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:_map = Counter(nums)_map = [(-v, i) for i, v in _map.items()]heapify(_map)res = []for i in range(k):want = heappop(_map)res.append(want[1])return res

方法二

Bucket Sort

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:_map = Counter(nums)freq = [[] for i in range(len(nums) + 1)]for key, val in _map.items():freq[val].append(key)res = []for i in range(len(freq) - 1, 0, -1):while freq[i] and k > 0:res.append(freq[i].pop())k -= 1if k == 0:breakreturn res