算法打卡day11

今日任务：

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 = 0
        right = k
        res = []
        while right <= len(nums):
            maxSum = max(nums[left:right])
            res.append(maxSum)
            left += 1
            right += 1
 
        return 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 heapq
 
class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        # 统计频率
        f = {}
        for i in nums:
            f[i] = f.get(i,0) + 1
 
        # 定义一个小顶堆，大小为k
        priority_queue = []
        for key,freq in f.items():
            heapq.heappush(priority_queue, (freq, key))
            if len(priority_queue) > k:  # 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                heapq.heappop(priority_queue)
 
        # 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组
        result = [0] * k
        for i in range(k - 1, -1, -1):
            # 将弹出小顶堆中第二个值key存放在列表中
            result[i] = heapq.heappop(priority_queue)[1]
        return result

感想：