优化滑动窗口中位数：Python双堆惰性删除法解决时间超限问题

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()

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