掌握滑动窗口中位数算法：LeetCode 480题解

在LeetCode 480题中，我们需要求出一个滑动窗口内元素的中位数。滑动窗口是一个固定大小的连续子数组，随着原数组的滑动而移动。要求在每个窗口位置，都能快速求出窗口内元素的中位数。

这个问题的一个直观解法是，每次滑动窗口时，都重新计算窗口内元素的中位数。然而，这种解法的时间复杂度较高，为O(nlogn)，在大数据量下效率较低。因此，我们需要寻找更高效的解法。

一个更高效的解法是使用双堆数据结构。双堆由一个大顶堆和一个小顶堆组成，大顶堆存储窗口内较小的一半元素，小顶堆存储较大的一半元素。这样，中位数就可以通过比较两个堆的堆顶元素来得到。为了保持堆的平衡，我们需要维护一些性质：

1. 当窗口内元素个数为奇数时，大顶堆的元素个数比小顶堆多一个，中位数就是大顶堆的堆顶元素；
2. 当窗口内元素个数为偶数时，大顶堆和小顶堆的元素个数相等，中位数就是大顶堆堆顶元素和小顶堆堆顶元素的平均值。

当窗口滑动时，我们需要将移出窗口的元素从双堆中删除，并将新滑入窗口的元素加入双堆。为了保证双堆的性质，我们需要对两个堆进行适当的调整。具体步骤如下：

1. 将新元素加入较小的堆中，如果两个堆都为空，则直接加入任意堆中；
2. 如果加入元素后，较小堆的元素个数比较大堆多两个，则将较小堆的堆顶元素弹出并加入较大堆中；
3. 如果加入元素后，较大堆的元素个数比较小堆多一个，则将较大堆的堆顶元素弹出并加入较小堆中。

这样，我们就可以在O(logn)的时间复杂度内求出每个窗口位置的中位数。下面是实现这个算法的Python代码：

import heapq
class MedianFinder:
    def __init__(self):
        self.lo = []  # 小顶堆
        self.hi = []  # 大顶堆
    def addNum(self, num: int) -> None:
        small = self.lo
        large = self.hi
        heapq.heappush(small, -heapq.heappushpop(large, num))
        if len(small) > len(large):
            heapq.heappush(large, -heapq.heappop(small))
    def findMedian(self) -> float:
        small = self.lo
        large = self.hi
        if len(large) > len(small):
            return float(large[0])
        return (large[0] - small[0]) / 2.0

这个算法的时间复杂度为O(nlogn)，其中n为滑动窗口的个数。由于双堆数据结构可以在O(logn)的时间内完成插入和删除操作，因此整个算法的时间复杂度较低。在实际应用中，这种算法可以处理大规模数据，并且具有较高的性能。

总之，通过双堆数据结构实现滑动窗口中位数算法，可以有效地降低时间复杂度，提高算法效率。在解决问题时，我们应该善于利用数据结构的特点，将问题转化为更简单的子问题，从而得到更好的解决方案。