优化滑动窗口中位数算法：双堆法的高效实现与性能瓶颈解决

import heapq

class Solution(object):
    # ... (__init__, balance, addNum, findMedian 略) ...

    def popNum(self, num):
        # 尝试从堆中移除元素
        if num > (self.small[0] * -1): # 判断元素在哪一个堆
            self.large.remove(num)    # 问题所在：list.remove()
            heapq.heapify(self.large) # 问题所在：heapify()
        else:
            self.small.remove(num * -1) # 问题所在：list.remove()
            heapq.heapify(self.small)   # 问题所在：heapify()

        self.balance() # 重新平衡堆

    # ... (medianSlidingWindow 略) ...

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:
            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):
        super(MaxWindowHeap, self).__init__(negate)

class Solution(object):
    def rebalance(self, add):
        """
        重新平衡两个堆的大小。
        add > 0 表示向某个堆添加了元素，需要重新平衡。
        add < 0 表示从某个堆移除了元素（逻辑上），需要重新平衡。
        """
        self.balance += add # 维护实际有效元素的数量差
        if abs(self.balance) < 2: # 如果平衡，无需操作
            return

        if self.balance > 1: # small堆元素过多
            self.small.push(self.large.pop()) # 从large弹出，推入small
        elif self.balance < -1: # large堆元素过多
            self.large.push(self.small.pop()) # 从small弹出，推入large
        self.balance = 0 # 重新平衡后，差值归零

    def insert(self, item):
        """
        向双堆结构中插入一个元素。
        """
        # 判断新元素应该进入哪个堆
        pivot = self.large.peek() # 优先看large堆顶（最小的大数）
        islarge = not pivot or item[0] > pivot[0] # 如果large为空或新元素大于large堆顶，则进入large

        heap = self.large if islarge else self.small
        heap.push(item)
        self.rebalance(1 if islarge else -1) # 更新平衡计数并尝试平衡

    def remove(self, item):
        """
        逻辑上移除一个元素（通过更新lowindex）。
        """
        # 判断要移除的元素在哪个堆
        pivot = self.large.peek()
        islarge = pivot and item[0] >= pivot[0] # 如果large不为空且元素大于等于large堆顶，则在large中

        # 关键步骤：更新两个堆的lowindex，标记所有索引小于item[1]+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 # 初始化平衡计数

        # 将原始数组转换为 (值, 索引) 元组列表
        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