【LeetCode 刷题】栈与队列(3)-队列的应用

此博客为《代码随想录》栈与队列章节的学习笔记，主要内容为队列的应用相关的题目解析。

文章目录

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

239. 滑动窗口最大值

题目链接

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = []
        # 未形成窗口
        for i in range(k):
            while q and q[-1] < nums[i]:
                q.pop()
            q.append(nums[i])
        res = [q[0]]
        # 形成窗口
        for i in range(len(nums) - k):
            # 出窗口
            if q[0] == nums[i]:
                q.pop(0)
            # 入窗口
            while q and q[-1] < nums[i + k]:
                q.pop()
            q.append(nums[i + k])
            res.append(q[0])
        return res

• 使用非严格递减单调队列
  • num 入窗口时，需要将队列中所有 < num 的元素弹出（注意不是 <=），再将 num 入队列
  • num 出窗口时，如果和队列头部相等，则队列头部也弹出

（图片源自 Krahets 的题解）

347. 前 K 个高频元素

题目链接

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        heap = []
        for key, val in count.items():
            if len(heap) >= k:
                if val > heap[0][0]:
                    heapq.heapreplace(heap, (val, key))
            else:
                heapq.heappush(heap, (val, key))
        return [item[1] for item in heap]

• 使用优先级队列（最小堆）：题目要求的是前 k 个高频元素，通过维护大小为 k 的最小堆，把已经不在前 k 频率的元素（堆顶元素）弹出，最终堆中只剩下前 k 个高频元素，时间复杂度 $O(n\log k)$
• Python 的 heapq 模块提供了一组操作，用于管理一个最小堆的数据结构：
  • heapq.heappush()：将一个元素插入到堆中，同时维护堆的特性
  • heapq.heapreplace()：将堆顶元素替换为一个新的元素，同时维护堆的特性
• 进入堆中的为元组，第一个元素为频率，第二个元素为对应的数字：由于 Python 比较元组时，Python 会从第一个元素开始逐个比较，因此会先比较频率，从而间接将频率作为优先级队列的比较关键字
• 注：for 循环的变量不能写 k, v，会和函数参数 k 冲突