优化滑动窗口中位数：使用惰性删除与双堆策略解决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()

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 item

def negate(item):  # 辅助函数，用于将 (值, 索引) 中的值取负
    return -item[0], item[1]

class MaxWindowHeap(MinWindowHeap):
    def __init__(self):
        super(MaxWindowHeap, self).__init__(negate) # 传入negate函数

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 result