滑动窗口最大值

阅读要点

• 使用最大堆维护滑动窗口，每次右移将元素加入堆
• 通过数组记录元素的值及其位置，堆顶元素不在窗口中则移除
• Python 中 heapq 默认最小堆，取负值实现最大堆
• 堆化时间复杂度 O(n)，入堆出堆 O(log n)

题目

239. 滑动窗口最大值 - 力扣（LeetCode）

解法一

思路

利用最大堆来维护滑动窗口。每次窗口右移时，将新元素加入堆中；同时，通过一个数组记录元素的值及其对应的位置。要获取滑动窗口中的最大值，只需检查堆顶元素是否仍在窗口内：若在，则直接取用；若不在，则将其移除，直到堆顶元素属于当前窗口。

答案

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)
        res = [-q[0][0]]
 
        for i in range(k, len(nums)):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heapq.heappop(q)
            res.append(-q[0][0])
        
        return res

收获

• 学习了 堆 这个数据结构及其在 Python 中的使用。

1. 堆的存储本质就是一个一维数组，在 Python 中可用 heapq.heapify(q) 将一个数组堆化，时间复杂度为 O(n)。
2. Python 中堆默认是最小堆，若想用最大堆可以取负值。
3. 可用 heapq.heappush 和 heapq.heappop 进行入堆和出堆操作。

解法二

剩余解法之后再更新。