1. 问题背景与双堆法基础
滑动窗口中位数问题要求在一个固定大小的窗口在数组上滑动时，实时计算并返回每个窗口内的中位数。双堆法是解决这类问题的经典策略，它维护两个堆：一个最大堆（small）存储较小的一半元素，一个最小堆（large）存储较大的一半元素。通过确保small堆的堆顶小于等于large堆的堆顶，并且两个堆的大小差异不超过1，可以高效地获取中位数。
- 当元素总数为奇数时，中位数通常是元素较多的那个堆的堆顶。
- 当元素总数为偶数时，中位数是两个堆堆顶的平均值。
2. 原始解决方案的性能瓶颈分析
在传统的双堆实现中，当滑动窗口移动时，需要移除窗口最左侧的元素并添加最右侧的新元素。原始解决方案中移除元素的代码通常如下所示：
def popNum(self, num):
if num > (self.small[0] * -1): # 假设small是最大堆，存储负值
self.large.remove(num)
heapq.heapify(self.large)
else:
self.small.remove(num * -1)
heapq.heapify(self.small)
self.balance()此处的关键问题在于 list.remove(num) 和 heapq.heapify()。 list.remove(num) 操作需要遍历列表以查找并删除指定元素，其时间复杂度为 O(N)，其中 N 是堆的大小。 在元素被移除后，堆的结构被破坏，因此需要调用 heapq.heapify() 来重建堆，这个操作的时间复杂度也是 O(N)。 对于一个包含 N 个元素，窗口大小为 K 的数组，总共有 N-K+1 个窗口。每个窗口的滑动都涉及一次 O(N) 的移除操作，导致整体时间复杂度飙升，在大规模输入（如 N=100000, K=50000）下极易导致时间超限（TLE）。
3. 优化策略：惰性删除法
为了解决 popNum 的效率问题，有两种主要的优化思路：
- 自定义堆实现：维护一个哈希表（字典），将每个值映射到其在堆列表中的索引。这样，当需要删除一个值时，可以通过哈希表快速找到其索引，然后用堆的最后一个元素替换它，再进行堆化（sift down/up）操作来恢复堆属性。这种方法可以将删除操作的时间复杂度降至 O(logN)。然而，这需要对 heapq 模块的内部函数进行重写或深度定制。
- 惰性删除（Lazy Deletion）：不立即从堆中物理删除元素，而是给它们打上“已删除”的标记。当从堆顶取元素时，如果发现它是已删除的元素，就将其弹出并忽略，直到找到一个未被删除的元素。
本文将重点采用第二种策略——惰性删除法，因为它在保持 heapq 接口的同时，能有效提升性能。
3.1 惰性删除法的实现细节
惰性删除法的核心思想是：
立即学习“Python免费学习笔记（深入）”；
- 唯一标识元素：由于数组中可能存在重复值，我们不能仅仅依靠值来判断一个元素是否在当前窗口内。因此，我们将每个元素存储为 (值, 索引) 的元组。
- 窗口边界作为删除标记：当滑动窗口向右移动时，最左侧的元素将离开窗口。我们无需立即从堆中移除这些元素。相反，我们维护一个 lowindex 变量，表示当前窗口的起始索引。任何索引小于 lowindex 的元素都被视为“已删除”或“不在当前窗口内”。
- 延迟弹出：当尝试从堆中获取堆顶元素时，如果堆顶元素的索引小于 lowindex，说明它已不在当前窗口内，应将其弹出并丢弃，然后继续检查新的堆顶，直到找到一个有效元素。
这种方法避免了昂贵的 list.remove() 和 heapq.heapify() 操作，因为插入和常规弹出操作的时间复杂度都是 O(logN)。虽然堆中可能会暂时保留一些已删除的元素，但它们最终会在 peek 或 pop 操作时被清理。
4. 优化后的代码实现与解析
以下是基于惰性删除策略的优化实现。
import heapq
# 辅助函数：用于实现最大堆，将(值, 索引)元组的值部分取反
def negate(item):
return -item[0], item[1]
# 最小堆的封装类，支持惰性删除
class MinWindowHeap(object):
def __init__(self, conv=lambda x: x):
self.heap = []
self.conv = conv # 转换函数，用于处理最大堆（值取反）
self.lowindex = 0 # 当前窗口的起始索引，用于标记已删除元素
def peek(self): # 返回堆顶的有效元素 (值, 索引)
while self.heap:
# conv函数将堆中存储的元素（可能已取反）转换回原始形式
item = self.conv(self.heap[0])
if item[1] >= self.lowindex: # 如果元素的索引在当前窗口内，则为有效元素
return item
# 否则，该元素已过期（已删除），从堆中弹出
heapq.heappop(self.heap)
return None # 堆为空或所有元素都已过期
def push(self, item): # 推入元素 (值, 索引)
heapq.heappush(self.heap, self.conv(item))
def pop(self): # 弹出堆顶的有效元素
item = self.peek() # 首先通过peek清理所有过期的元素
if item:
heapq.heappop(self.heap) # 弹出当前有效的堆顶
return item
# 最大堆的封装类，继承自MinWindowHeap，并使用negate函数实现最大堆行为
class MaxWindowHeap(MinWindowHeap):
def __init__(self):
# Python 3中super()可以不带参数，这里兼容Python 2/3写法
super(MaxWindowHeap, self).__init__(negate)
class Solution(object):
def rebalance(self, add):
"""
重新平衡两个堆的大小。
balance变量记录了large堆相对于small堆的净增元素数。
如果balance绝对值超过1，则进行平衡操作。
"""
self.balance += add
if abs(self.balance) < 2:
return
if self.balance > 1: # large堆过大，将large堆顶移到small堆
self.small.push(self.large.pop())
elif self.balance < -1: # small堆过大，将small堆顶移到large堆
self.large.push(self.small.pop())
self.balance = 0 # 平衡后重置balance
def insert(self, item):
"""
将新元素插入到合适的堆中。
"""
pivot = self.large.peek() # 尝试获取large堆顶作为判断基准
# 如果large堆为空，或新元素小于等于small堆顶（即large.peek()），则插入small堆
# 注意：这里需要更严谨的判断，如果large.peek()为None，则pivot为None，islarge为False，插入small
# 实际逻辑是：如果item小于等于small堆顶，则插入small；否则插入large
# 简化判断：如果large堆顶存在且item大于large堆顶，则插入large；否则插入small
islarge = not pivot or item[0] > pivot[0]
heap = self.large if islarge else self.small
heap.push(item)
self.rebalance(1 if islarge else -1) # 更新balance并尝试平衡
def remove(self, item):
"""
通过更新lowindex来“惰性删除”元素。
"""
pivot = self.large.peek()
# 判断被移除的元素原本在哪一个堆中
islarge = pivot and item[0] >= pivot[0]
# 更新两个堆的lowindex，所有索引小于item[1]+1的元素都被视为已删除
self.large.lowindex = self.small.lowindex = item[1] + 1
self.rebalance(-1 if islarge else 1) # 更新balance并尝试平衡
def getMedian(self):
"""
计算当前窗口的中位数。
"""
if self.balance == 0: # 两个堆大小相等
return (self.large.peek()[0] + self.small.peek()[0]) * 0.5
# 某个堆多一个元素，中位数就是那个堆的堆顶
return self.large.peek()[0] if self.balance > 0 else self.small.peek()[0]
def medianSlidingWindow(self, nums, k):
"""
滑动窗口中位数主函数。
"""
self.small = MaxWindowHeap() # 最大堆
self.large = MinWindowHeap() # 最小堆
self.balance = 0 # 平衡因子，large堆元素数 - small堆元素数
# 将原始数组转换为 (值, 索引) 元组列表
items = [(val, i) for i, val in enumerate(nums)]
# 初始化第一个窗口
for item in items[:k]:
self.insert(item)
result = [self.getMedian()]
# 滑动窗口
# olditem 是即将离开窗口的元素
# item 是即将进入窗口的元素
for olditem, item in zip(items, items[k:]):
self.remove(olditem) # 惰性删除旧元素
self.insert(item) # 插入新元素
result.append(self.getMedian()) # 计算并记录当前窗口中位数
return result
4.1 代码解析
negate(item) 辅助函数： 用于将 (值, 索引) 元组的值部分取反，以便 heapq 模块能将最小堆行为应用于最大堆（通过存储负值实现）。
-
MinWindowHeap 类：
- __init__(self, conv=lambda x: x)：初始化一个空堆 self.heap，conv 是转换函数（默认不转换，用于最小堆；对于最大堆则传入 negate）。self.lowindex 记录当前窗口的起始索引，任何索引小于此值的元素都视为过期。
- peek()：此方法是惰性删除的关键。它循环检查堆顶元素，如果其索引小于 self.lowindex，则说明该元素已过期，将其弹出。直到找到一个有效元素或堆为空。
- push(item)：将 (值, 索引) 元组通过 conv 函数处理后推入堆。
- pop()：先调用 peek() 清理过期元素，然后弹出并返回当前有效的堆顶元素。
MaxWindowHeap 类： 继承自 MinWindowHeap，并通过 super().__init__(negate) 将 negate 函数作为转换函数传入，从而实现最大堆的功能。
-
Solution 类：
- rebalance(self, add)：负责维护 small 和 large 两个堆的大小平衡。self.balance 记录 large 堆相对于 small 堆的元素数量差。当 abs(self.balance) 超过 1 时，会将一个堆的堆顶元素移动到另一个堆，以恢复平衡。
- insert(self, item)：将新的 (值, 索引) 元组插入到 small 或 large 堆中，并调用 rebalance。判断插入哪个堆的逻辑是：如果 item[0] 大于 large 堆的堆顶（如果 large 堆不为空），则插入 large 堆；否则插入 small 堆。
- remove(self, item)：这是惰性删除的核心。它不直接从堆中移除 item，而是通过更新 self.large.lowindex 和 self.small.lowindex 为 item[1] + 1，来标记所有索引小于 item[1] + 1 的元素为过期。这意味着 item 及其之前的所有元素都已离开当前窗口。然后调用 rebalance。
- getMedian(self)：根据 self.balance 的值，返回当前窗口的中位数。
- medianSlidingWindow(self, nums, k)：主函数。首先将输入数组 nums 转换为 (值, 索引) 元组列表。然后初始化第一个窗口，计算其第一个中位数。接着通过循环滑动窗口，对离开窗口的元素调用 remove，对进入窗口的元素调用 insert，并记录每个窗口的中位数。
5. 总结与注意事项
- 时间复杂度：惰性删除法将单次插入和（有效）删除操作的时间复杂度都优化到了 O(logK)，其中 K 是窗口大小。因此，对于 N 个元素的数组，总的时间复杂度为 O(N logK)。这在大规模数据下显著优于 O(N^2) 或 O(NK) 的朴素解法。
- 空间复杂度：由于堆中可能暂时保留一些已删除的元素，最坏情况下，堆的大小可能达到 O(N)。但通常情况下，随着窗口的滑动，过期元素会被逐渐清理，实际空间占用接近 O(K)。
- Python 2/3 super() 兼容性：在 MaxWindowHeap 的 __init__ 方法中，super(MaxWindowHeap, self).__init__(negate) 是兼容 Python 2 和 Python 3 的写法。在 Python 3 中，super().__init__(negate) 也可以工作。
- 理解 balance 变量：self.balance 追踪的是 large 堆相对于 small 堆的“有效”元素数量差。每次插入或移除元素时，需要根据元素所属的堆来更新 balance。
- 惰性删除的优势：避免了在堆中查找和物理删除元素的复杂性，简化了代码逻辑，并提升了性能。其代价是堆的实际大小可能略大于有效元素数量，但通常不会导致内存问题。
通过采用惰性删除策略，我们可以高效地解决滑动窗口中位数问题，即使面对大规模输入数据也能保持良好的性能。
