LeetCode 480题 “Sliding Window Median” 是一个中等难度的题目，要求我们在一个滑动窗口中找到中位数。中位数是指在一个有序数组中位于中间位置的数，如果数组长度是奇数，则中位数是中间那个数；如果数组长度是偶数，则中位数是中间两个数的平均值。

题目描述

给定一个数组 nums 和一个整数 k，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口的中位数数组。

示例

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [1,-1,-1,3,5,6] 解释:

[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

解题思路

要解决这个问题，我们可以使用两个数据结构：一个大顶堆（max heap）和一个小顶堆（min heap）。大顶堆用来存储窗口中较小的那一半元素，小顶堆用来存储较大的那一半元素。这样，我们可以保证：

• 大顶堆中的所有元素都小于等于小顶堆中的所有元素。
• 两个堆的大小之差不超过1。

通过这种方式，我们可以快速找到中位数：

• 如果两个堆的大小相等，中位数是两个堆顶元素的平均值。
• 如果两个堆的大小不相等，中位数是较大的那个堆的堆顶元素。

具体步骤

1. 初始化：创建一个大顶堆 left 和一个小顶堆 right。
2. 填充初始窗口：将前 k 个元素加入堆中，调整堆使其满足上述条件。
3. 滑动窗口：从第 k 个元素开始，每次移动窗口时：
   • 移除窗口最左边的元素。
   • 添加窗口最右边的元素。
   • 调整堆使其满足上述条件。
   • 计算当前窗口的中位数并记录。

代码实现

以下是使用Python实现的代码：

import heapq

def remove_num(num):
    if num <= -left[0]:
        left.remove(-num)
        heapq.heapify(left)
    else:
        right.remove(num)
        heapq.heapify(right)
    balance()

def balance():
    if len(left) > len(right) + 1:
        heapq.heappush(right, -heapq.heappop(left))
    if len(right) > len(left):
        heapq.heappush(left, -heapq.heappop(right))

def get_median():
    if len(left) == len(right):
        return (-left[0] + right[0]) / 2
    else:
        return -left[0]

left, right = [], []
result = []

for i in range(len(nums)):
    add_num(nums[i])
    if i >= k:
        remove_num(nums[i - k])
    if i >= k - 1:
        result.append(get_median())

return result

nums = [1,3,-1,-3,5,3,6,7] k = 3 print(medianSlidingWindow(nums, k)) # 输出: [1, -1, -1, 3, 5, 6]

解释

1. add_num(num)：将一个数加入堆中，并根据需要调整堆。
2. remove_num(num)：从堆中移除一个数，并重新调整堆。
3. balance()：确保两个堆的大小之差不超过1。
4. get_median()：根据两个堆的顶元素计算中位数。

通过这种方式，我们可以在每个窗口移动时高效地计算中位数，从而解决这道题目。