算法通关村第十六关：黄金挑战：滑动窗口与堆结合

黄金挑战：滑动窗口与堆结合

堆的大小一般是有限的，能直接返回当前位置下的最大值或者最小值
该特征与滑动窗口结合，可以解决一些特定场景的问题

1. 滑动窗口与堆问题的结合

LeetCode239
https://leetcode.cn/problems/sliding-window-maximum/

思路分析

对于最大值，K个最大这种场景，优先队列（堆）是首先该考虑的思路。
大根堆可以帮我们实时维护一系列元素的最大值

具体执行：

• 先将数组的前K个元素放入大根堆中，此时最大值为堆顶元素
• 每当窗口右移时，将新元素放入大根堆中，此时最大值可能不在滑动窗口中
  最大值为滑动窗口的前一个元素，此时需要将堆顶元素移除，直到堆顶元素在滑动窗口中
  最大值为滑动窗口中的元素，此时最大值就是堆顶元素
• 为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在有限队列中存储二元组(num, index)，表示元素 num 在数组中的下标为 index

代码实现

import heapq

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        ans = []
        # 注意 Python 默认的优先队列是小根堆
        # pyhton 中（int,int）可正常比较大小 (1, 0) < (2, 0), (1, 0) < (1, 1)
        heap = [(-nums[i], i) for i in range(k)]
        heapq.heapify(heap)

        ans.append(-heap[0][0])
        for i in range(n-k):
            heapq.heappush(heap, (-nums[i+k], i+k))
            # 移除堆顶元素，直到堆顶元素在滑动窗口中
            while heap[0][1] <= i:
                heapq.heappop(heap)
            ans.append(-heap[0][0])

        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20