本题使用两个堆(大顶堆和小顶堆)来维护滑动窗口内的元素,并通过平衡两个堆的大小来计算中位数。具体思路如下:
1. 初始化大顶堆smaller和小顶堆bigger,用于存储滑动窗口内的元素。
2. 遍历数组nums,对于每个元素num:
- 如果当前下标i>=k,说明滑动窗口向右移动,需要移除窗口最左边的元素nums[i-k],更新balance值。
- 根据num与堆顶元素的大小关系,将num插入到合适的堆中,并通过调整两个堆的大小来保持平衡。
- 如果当前下标i<k-1,说明还未形成完整的滑动窗口,继续遍历下一个元素。
- 移除堆顶失效的元素(即在窗口外的元素),并更新balance值。
- 根据两个堆的大小关系,计算当前窗口的中位数,并将其加入结果数组res中。
3. 返回结果数组res。
时间复杂度: O(nlogk)
空间复杂度: O(n)
```python
import heapq
from collections import defaultdict
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
mp = defaultdict(int) # 哈希表,用于记录元素出现次数
bigger = [] # 小顶堆,存储较大的一半元素
smaller = [] # 大顶堆,存储较小的一半元素
balance = 0 # 平衡因子,用于维护两个堆的大小关系
res = [] # 结果数组,存储每个窗口的中位数
for i, num in enumerate(nums):
if i >= k:
# 滑动窗口向右移动,移除最左边的元素
mp[nums[i-k]] += 1
if nums[i-k] <= -smaller[0]:
balance -= 1
else:
balance += 1
if not smaller or -smaller[0] >= num:
# 将当前元素插入到smaller中
heapq.heappush(smaller, -num)
if len(smaller) + balance > 1 + len(bigger):
# 调整两个堆的大小,保持平衡
heapq.heappush(bigger, -heapq.heappop(smaller))
else:
# 将当前元素插入到bigger中
heapq.heappush(bigger, num)
if len(smaller) + balance < len(bigger):
# 调整两个堆的大小,保持平衡
heapq.heappush(smaller, -heapq.heappop(bigger))
if i < k - 1:
# 还未形成完整的滑动窗口,继续遍历下一个元素
continue
while smaller and mp[-smaller[0]]:
# 移除smaller中失效的元素
mp[-smaller[0]] -= 1
heapq.heappop(smaller)
balance += 1
while bigger and mp[bigger[0]]:
# 移除bigger中失效的元素
mp[bigger[0]] -= 1
heapq.heappop(bigger)
balance -= 1
if len(smaller) + balance == len(bigger):
# 两个堆大小相等,中位数为两个堆顶元素的平均值
res.append((bigger[0] - smaller[0]) / 2)
else:
# 两个堆大小不相等,中位数为smaller的堆顶元素
res.append(-smaller[0])
return res
```