今日任务：
1）239. 滑动窗口最大值
2）347.前 K 个高频元素
239. 滑动窗口最大值
题目链接：239. 滑动窗口最大值 - 力扣（LeetCode）
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
---------------------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
--------------------------------------------示例 2：
输入：nums = [1], k = 1
输出：[1]
文章讲解：代码随想录 (programmercarl.com)
视频讲解：单调队列正式登场！| LeetCode：239. 滑动窗口最大值哔哩哔哩bilibili
方法一：暴力解法思路
直接采用双指针循环遍历数组，每次取出滑动窗口中最大值，提交超时，时间复杂度为O(kn)
class Solution:# 暴力解法，超时，时间复杂度O(kn)def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:left = 0right = kres = []while right <= len(nums):maxSum = max(nums[left:right])res.append(maxSum)left += 1right += 1return res方法二：采用单调队列
1）首先，我们需要自己实现单调队列，队列中只维护最大值即可。队列是先进先出，那我们队列长度控制为k。
2）当进来一个数时，比较其与队列中最后一个数的大小
若新增数大，则弹出队列中的的数。
若队列中的数大，则添加新增数
3）当队列中满k个元素时，我们需要将最前面的元素弹出，同时新增一个数，重复2）过程
class Solution:def maxSlidingWindow2(self, nums: list[int], k: int) -> list[int]:q = MyQueue()res = []# 将前k个元素放进队列for i in nums[:k]:q.push(i)# 收集最大值res.append(q.getMax())for i in range(k,len(nums)):# 移除窗口最前面的元素q.pop(nums[i-k])# 新增元素q.push(nums[i])# 获得当前最大元素,将最大值添加到列表中res.append(q.getMax())return res# 定义一个单调队列
class MyQueue():def __init__(self):# 使用deque实现单调队列self.queue = deque()def pop(self,value):if self.queue and value == self.queue[0]:self.queue.popleft()def push(self,value):while self.queue and value > self.queue[-1]:self.queue.pop()self.queue.append(value)def getMax(self):return self.queue[0]感想：
这题核心是要用单调队列结构。如果不熟悉这个结构就比较难。所以还是的反复做题，多熟悉数据结构
347.前 K 个高频元素
题目链接：347. 前 K 个高频元素 - 力扣（LeetCode）
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]示例 2:
输入: nums = [1], k = 1
输出: [1]
文章讲解：代码随想录 (programmercarl.com)
视频讲解：优先级队列正式登场！大顶堆、小顶堆该怎么用？| LeetCode：347.前 K 个高频元素哔哩哔哩bilibili
思路：
1）首先先用map求频率
2）然后采用优先队列去对频率排序，维护前k个元素，有一点要注意，应该采用小顶堆实现，每次弹出堆顶的最小数，把大数留下来
import heapqclass Solution:def topKFrequent(self, nums: list[int], k: int) -> list[int]:# 统计频率f = {}for i in nums:f[i] = f.get(i,0) + 1# 定义一个小顶堆，大小为kpriority_queue = []for key,freq in f.items():heapq.heappush(priority_queue, (freq, key))if len(priority_queue) > k: # 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为kheapq.heappop(priority_queue)# 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组result = [0] * kfor i in range(k - 1, -1, -1):# 将弹出小顶堆中第二个值key存放在列表中result[i] = heapq.heappop(priority_queue)[1]return result
感想：
