优化滑动窗口中位数：使用延迟删除和双堆方法解决Python TLE问题

def popNum(self, num):
    if num > (self.small[0] * -1): # 假设small[0]是最大堆的堆顶，其真实值是负数
        self.large.remove(num)
        heapq.heapify(self.large)
    else:
        self.small.remove(num * -1)
        heapq.heapify(self.small)
    self.balance()

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  # 转换函数 (例如，用于MaxHeap取反值)
        self.lowindex = 0  # 窗口下限索引，用于识别已删除项

    def peek(self):  # 返回 (值, 索引) 或 None (如果堆为空或仅包含已删除项)
        while self.heap:
            # 转换堆顶元素，例如 MaxWindowHeap 会将值取反
            item = self.conv(self.heap[0]) 
            if item[1] >= self.lowindex: # 如果索引在当前窗口内，则有效
                return item
            # 元素已过期（索引小于lowindex），从堆中弹出
            heapq.heappop(self.heap)
        return None # 堆中没有有效元素

    def push(self, item):
        # 将 (值, 索引) 对通过转换函数推入堆
        heapq.heappush(self.heap, self.conv(item))

    def pop(self):
        item = self.peek()  # 获取有效堆顶，同时清除所有过期的堆顶
        if item:
            heapq.heappop(self.heap) # 实际弹出有效堆顶
        return item # 返回被弹出的有效元素

class MaxWindowHeap(MinWindowHeap):
    def __init__(self):
        # Python 3 中 super() 可以不带参数
        super(MaxWindowHeap, self).__init__(negate) # 使用negate函数将最小堆模拟为最大堆

class Solution(object):
    def rebalance(self, add):
        """
        调整两个堆的平衡。
        add > 0 表示 large 堆增加了元素，或 small 堆移除了元素。
        add < 0 表示 small 堆增加了元素，或 large 堆移除了元素。
        """
        self.balance += add
        if abs(self.balance) < 2: # 堆已平衡 (大小差不超过1)
            return

        if self.balance > 1: # large 堆元素过多，需要移动一个到 small 堆
            self.small.push(self.large.pop())
        elif self.balance < -1: # small 堆元素过多，需要移动一个到 large 堆
            self.large.push(self.small.pop())
        self.balance = 0 # 重新平衡后，balance 归零

    def insert(self, item):
        """
        将新元素插入到合适的堆中并调整平衡。
        item 是 (值, 索引) 对。
        """
        # 尝试获取 large 堆的堆顶作为枢轴，如果 large 堆为空，则使用 small 堆的堆顶
        pivot = self.large.peek() 

        # 判断新元素应该放入 large 堆还是 small 堆
        # 如果 large 堆为空，或新元素大于等于 large 堆的堆顶，则放入 large 堆
        islarge = (pivot is None) or (item[0] >= pivot[0])
        heap = self.large if islarge else self.small
        heap.push(item)

        # 更新平衡计数并重新平衡
        self.rebalance(1 if islarge else -1)

    def remove(self, item):
        """
        逻辑删除一个元素（通过更新 lowindex 标记过期）并调整平衡。
        item 是 (值, 索引) 对，表示离开窗口的旧元素。
        """
        # 获取 large 堆的堆顶作为枢轴
        pivot = self.large.peek()
        # 判断旧元素是属于 large 堆还是 small 堆
        islarge = (pivot is not None) and (item[0] >= pivot[0])

        # 关键步骤：更新两个堆的 lowindex，标记所有索引小于等于 item[1] 的元素为过期
        # 这意味着窗口向右移动了，item[1] 及其之前的所有元素都可能已过期
        self.large.lowindex = self.small.lowindex = item[1] + 1

        # 更新平衡计数并重新平衡
        self.rebalance(-1 if islarge else 1)

    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):
        """
        滑动窗口中位数的主函数。
        :type nums: List[int]
        :type k: int
        :rtype: List[float]
        """
        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