What data structure pattern is essential for Sliding Window Median?

Dual heaps (max-heap and min-heap) combined with a hash map for lazy deletions form the core pattern to retrieve medians efficiently.

How do I handle even-sized windows?

For even-length windows, compute the median as the average of the top of the max-heap and min-heap after rebalancing.

Is sorting each window a valid approach?

Sorting each window works but is inefficient; it leads to O(n k log k) time complexity and fails for large arrays.

How do hash maps assist heaps in this problem?

Hash maps track elements marked for removal, allowing heaps to lazily remove outdated values without costly re-heapification.

Can Sliding Window Median be solved with a single heap?

A single heap cannot efficiently provide median while supporting arbitrary deletions; dual heaps are required to maintain balance.

#480

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

滑动窗口中位数

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。例如： [2,3,4] ，中位数是 3 [2,3] ，中位数是 (2 + 3) / 2 = 2.5 给你一个数组 nums ，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数…

数组哈希表滑动窗口堆（优先队列）

题目描述

中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

例如：

[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5

给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

示例：

给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。

窗口位置                      中位数
---------------               -----
[1  3  -1] -3  5  3  6  7       1
 1 [3  -1  -3] 5  3  6  7      -1
 1  3 [-1  -3  5] 3  6  7      -1
 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]      6

因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。

提示：

你可以假设 k 始终有效，即：k 始终小于等于输入的非空数组的元素个数。
与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。

lightbulb

解题思路

方法一：双优先队列（大小根堆） + 延迟删除

我们可以使用两个优先队列（大小根堆）维护当前窗口中的元素，其中一个优先队列存储当前窗口中较小的一半元素，另一个优先队列存储当前窗口中较大的一半元素。这样，当前窗口的中位数就是两个优先队列的堆顶元素的平均值或其中的一个。

我们设计一个类 $\textit{MedianFinder}$ ，用于维护当前窗口中的元素。该类包含以下方法：

add_num(num)：将 $\textit{num}$ 加入当前窗口中。
find_median()：返回当前窗口中元素的中位数。
remove_num(num)：将 $\textit{num}$ 从当前窗口中移除。
prune(pq)：如果堆顶元素在延迟删除字典 $\textit{delayed}$ 中，则将其从堆顶弹出，并从该元素的延迟删除次数中减一。如果该元素的延迟删除次数为零，则将其从延迟删除字典中删除。
rebalance()：如果较小的一半元素的数量比较大的一半元素的数量多 $2$ 个，则将较大的一半元素的堆顶元素加入较小的一半元素中；如果较小的一半元素的数量比较大的一半元素的数量少，则将较大的一半元素的堆顶元素加入较小的一半元素中。

在 add_num(num) 方法中，我们先考虑将 $\textit{num}$ 加入较小的一半元素中，如果 $\textit{num}$ 大于较大的一半元素的堆顶元素，则将 $\textit{num}$ 加入较大的一半元素中。然后我们调用 rebalance() 方法，使得两个优先队列的大小之差不超过 $1$ 。

在 remove_num(num) 方法中，我们将 $\textit{num}$ 的延迟删除次数加一。然后我们将 $\textit{num}$ 与较小的一半元素的堆顶元素进行比较，如果 $\textit{num}$ 小于等于较小的一半元素的堆顶元素，则更新较小的一半元素的大小，并且调用 prune() 方法，使得较小的一半元素的堆顶元素不在延迟删除字典中。否则，我们更新较大的一半元素的大小，并且调用 prune() 方法，使得较大的一半元素的堆顶元素不在延迟删除字典中。

在 find_median() 方法中，如果当前窗口的大小为奇数，则返回较小的一半元素的堆顶元素；否则，返回较小的一半元素的堆顶元素与较大的一半元素的堆顶元素的平均值。

在 prune(pq) 方法中，如果堆顶元素在延迟删除字典中，则将其从堆顶弹出，并从该元素的延迟删除次数中减一。如果该元素的延迟删除次数为零，则将其从延迟删除字典中删除。

在 rebalance() 方法中，如果较小的一半元素的数量比较大的一半元素的数量多 $2$ 个，则将较大的一半元素的堆顶元素加入较小的一半元素中；如果较小的一半元素的数量比较大的一半元素的数量少，则将较大的一半元素的堆顶元素加入较小的一半元素中。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

class MedianFinder:
    def __init__(self, k: int):
        self.k = k
        self.small = []
        self.large = []
        self.delayed = defaultdict(int)
        self.small_size = 0
        self.large_size = 0

    def add_num(self, num: int):
        if not self.small or num <= -self.small[0]:
            heappush(self.small, -num)
            self.small_size += 1
        else:
            heappush(self.large, num)
            self.large_size += 1
        self.rebalance()

    def find_median(self) -> float:
        return -self.small[0] if self.k & 1 else (-self.small[0] + self.large[0]) / 2

    def remove_num(self, num: int):
        self.delayed[num] += 1
        if num <= -self.small[0]:
            self.small_size -= 1
            if num == -self.small[0]:
                self.prune(self.small)
        else:
            self.large_size -= 1
            if num == self.large[0]:
                self.prune(self.large)
        self.rebalance()

    def prune(self, pq: List[int]):
        sign = -1 if pq is self.small else 1
        while pq and sign * pq[0] in self.delayed:
            self.delayed[sign * pq[0]] -= 1
            if self.delayed[sign * pq[0]] == 0:
                self.delayed.pop(sign * pq[0])
            heappop(pq)

    def rebalance(self):
        if self.small_size > self.large_size + 1:
            heappush(self.large, -heappop(self.small))
            self.small_size -= 1
            self.large_size += 1
            self.prune(self.small)
        elif self.small_size < self.large_size:
            heappush(self.small, -heappop(self.large))
            self.large_size -= 1
            self.small_size += 1
            self.prune(self.large)


class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        finder = MedianFinder(k)
        for x in nums[:k]:
            finder.add_num(x)
        ans = [finder.find_median()]
        for i in range(k, len(nums)):
            finder.add_num(nums[i])
            finder.remove_num(nums[i - k])
            ans.append(finder.find_median())
        return ans

speed

复杂度分析

指标	值
时间	complexity is O(n log k) due to insertion and deletion in heaps for each of the n-k+1 windows. Space complexity is O(k) for the two heaps and hash map storing delayed deletions.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Will you maintain the sorted order of the window explicitly or implicitly?
question_mark
How do you handle deletions from a heap efficiently when the window moves?
question_mark
Can you explain why dual heaps are necessary instead of a single priority queue?

warning

常见陷阱

外企场景

error
Attempting to sort the window each step, leading to O(n k log k) time.
error
Forgetting to rebalance heaps after insertions and deletions, causing incorrect median computation.
error
Not accounting for even-length windows where median is the average of two middle numbers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the median in a circular sliding window where the array wraps around.
arrow_right_alt
Find the k-th smallest element in each sliding window instead of the median.
arrow_right_alt
Handle dynamic updates to nums in addition to sliding the window.

help

常见问题

外企场景

继续练习

#632 最小区间 #594 最长和谐子序列 #347 前 K 个高频元素