1. 问题背景与双堆法基础
滑动窗口中位数问题要求在一个固定大小k的滑动窗口在数组上移动时，计算每个窗口内的中位数。双堆法是解决此问题的常用且高效策略：
- 小顶堆 (Min-Heap): 存储窗口中较大的k/2个元素。
- 大顶堆 (Max-Heap): 存储窗口中较小的k/2个元素。
通过维护这两个堆，使得大顶堆的堆顶元素小于或等于小顶堆的堆顶元素，并且两个堆的大小差不超过1。这样，中位数可以直接从堆顶元素中获取。
2. TLE错误分析：低效的元素移除
在原始的双堆实现中，当窗口滑动时，需要移除窗口最左侧的元素，并添加最右侧的新元素。问题通常出现在移除旧元素的操作上：
def popNum(self, num):
if num > (self.small[0] * -1):
self.large.remove(num) # O(K) 查找和移除
heapq.heapify(self.large) # O(K) 重新堆化
else:
self.small.remove(num * -1) # O(K) 查找和移除
heapq.heapify(self.small) # O(K) 重新堆化
self.balance()list.remove(num) 操作在Python中需要遍历列表来查找元素，其时间复杂度为O(K)（K为堆的大小）。移除元素后，堆的结构被破坏，需要调用heapq.heapify()来重新构建堆，这同样是O(K)的操作。因此，每次移除元素的总时间复杂度为O(K)。
对于包含N个元素的数组和大小为K的窗口，总时间复杂度将是O(N * K)，当N和K都很大时（例如N=100000, K=50000），这将导致严重的时间限制超出（TLE）。
3. 优化方案：惰性删除与索引跟踪
为了将移除操作的复杂度降低到O(log K)，我们采用以下策略：
3.1 惰性删除 (Lazy Deletion)
与其在堆中物理移除元素，不如采用“惰性删除”策略：
- 不实际移除元素： 当一个元素离开滑动窗口时，我们不在堆中直接将其删除。
- 标记删除： 我们通过某种机制来“标记”这些元素为已删除或无效。
- 跳过无效元素： 当我们尝试从堆中获取堆顶元素（peek或pop）时，检查该元素是否已被标记为无效。如果是，则将其弹出并忽略，直到找到一个有效的堆顶元素。
3.2 唯一标识元素：(值, 索引) 元组
由于数组中可能存在重复值，仅仅通过值来判断元素是否在窗口外是不够的。例如，窗口中可能有多个5，当一个5离开窗口时，我们不能错误地删除另一个仍在窗口中的5。
解决方案是，将每个元素存储为(值, 原始索引)的元组。这样，每个元素在堆中都有一个唯一的标识符。
3.3 动态窗口与lowindex
为了实现惰性删除，我们可以利用滑动窗口的特性。当窗口从[start, end]移动到[start+1, end+1]时，元素nums[start]离开窗口。我们可以设置一个lowindex，表示当前窗口的起始索引。任何索引小于lowindex的元素都应被视为已删除。
4. 优化实现细节
我们将构建两个自定义的堆类MinWindowHeap和MaxWindowHeap，它们基于Python的heapq模块，并加入了惰性删除逻辑。
4.1 MinWindowHeap 类
import heapq
class MinWindowHeap(object):
def __init__(self, conv=lambda x: x):
self.heap = [] # 存储 (值, 索引) 元组的堆
self.conv = conv # 转换函数，用于MaxHeap将值取负
self.lowindex = 0 # 当前窗口的起始索引，小于此索引的元素被视为已删除
def peek(self):
"""返回堆顶的有效元素，跳过所有已删除的元素。"""
while self.heap:
item = self.conv(self.heap[0]) # 获取堆顶元素（可能经过转换）
if item[1] >= self.lowindex: # 如果元素的索引大于等于lowindex，则为有效元素
return item
heapq.heappop(self.heap) # 否则，该元素已过期，将其弹出并继续查找
def push(self, item):
"""将 (值, 索引) 元组推入堆中。"""
heapq.heappush(self.heap, self.conv(item))
def pop(self):
"""弹出并返回堆顶的有效元素。"""
item = self.peek() # 先通过peek找到并移除所有无效元素
heapq.heappop(self.heap) # 弹出有效的堆顶元素
return item4.2 MaxWindowHeap 类
MaxWindowHeap通过对值取负来实现大顶堆的功能，其余逻辑与MinWindowHeap相同。
def negate(item): # 辅助函数，用于将 (值, 索引) 中的值取负
return -item[0], item[1]
class MaxWindowHeap(MinWindowHeap):
def __init__(self):
super(MaxWindowHeap, self).__init__(negate) # 传入negate函数4.3 Solution 类：滑动窗口中位数逻辑
Solution类将协调两个自定义堆的操作，实现滑动窗口中位数的计算。
class Solution(object):
def rebalance(self, add):
"""
重新平衡两个堆的大小。
balance > 0 表示 large 堆元素多，balance < 0 表示 small 堆元素多。
"""
self.balance += add
if abs(self.balance) < 2: # 堆大小差在1以内，无需平衡
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() or self.small.peek() # 找到一个参考点来决定插入哪个堆
islarge = not pivot or item[0] > pivot[0] # 如果新元素大于参考点，则属于large堆
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 # 用于跟踪两个堆的有效元素数量差
# 将原始数组转换为 (值, 索引) 元组列表
items = [(val, i) for i, val in enumerate(nums)]
# 初始化第一个窗口
for item in items[:k]:
self.insert(item)
result = [self.getMedian()]
# 滑动窗口
for olditem, item in zip(items, items[k:]):
self.remove(olditem) # 移除旧元素（惰性删除）
self.insert(item) # 插入新元素
result.append(self.getMedian()) # 获取当前窗口中位数
return result5. 优化后的时间复杂度分析
- 插入 (insert): heapq.heappush 是 O(log K)。
- 移除 (remove): remove 操作本身只是更新lowindex，是O(1)。后续的rebalance操作中可能涉及pop和push，这些是O(log K)。
- 获取中位数 (getMedian): peek 操作在最坏情况下可能需要弹出所有无效元素，但由于每个元素只会被推入堆一次，并被弹出一次（无论是否有效），所以peek和pop的摊还时间复杂度仍为O(log K)。
- 总时间复杂度: 每个窗口操作（插入、移除、获取中位数）的摊还时间复杂度为O(log K)。由于有N-K+1个窗口，所以总时间复杂度为O(N log K)。
相比于原始的O(N * K)复杂度，O(N log K)在处理大数据集时具有显著的性能优势，能够有效避免TLE。
6. 注意事项与总结
- Python版本兼容性： 示例代码中的super(MaxWindowHeap, self).__init__(negate)在Python 2和Python 3中均可运行。在Python 3中，super().__init__(negate)也可以工作。
- balance变量： balance变量用于跟踪两个堆中有效元素的相对数量，确保它们保持平衡，这对于正确计算中位数至关重要。
- 惰性删除的内存开销： 惰性删除意味着堆中可能存在一些已过期但尚未被物理移除的元素。在极端情况下，如果窗口很小而数组很大，堆的大小可能会略大于K。但由于每个元素最终都会被弹出，并且peek/pop操作会清理无效元素，这种额外的内存开销通常是可接受的，且远低于效率提升带来的好处。
- 通用性： 惰性删除结合索引跟踪的方法不仅适用于滑动窗口中位数，也适用于其他需要高效在数据结构中“删除”元素的滑动窗口问题。
通过上述优化，我们成功解决了滑动窗口中位数问题中因低效移除操作导致的TLE问题，提供了一个既高效又健壮的解决方案。
