LeetCode 480. 滑动窗口中位数
目录
题目描述
题意分析
给定长度为 $n$ 的整数数组和固定窗口长度
k，窗口从最左端起每次右移一位，要求依次输出每个窗口内k个数的中位数。k为奇数时中位数是排序后正中间那个数，为偶数时是中间两个数的平均值，所以返回值必须是浮点数组。有两个约束值得注意。其一，元素取值可以到 $\pm 2^{31}$ 量级，偶数窗口求平均时两个极端值相加会越过 32 位整数的表示范围，必须提前扩宽再除。其二，窗口只在两端变化，每次右移只走掉一个旧元素、进来一个新元素，中间 $k-1$ 个元素完全不变——这正是不该每个窗口都从头排序的信号。
边界情形包括：
k等于 1 时每个窗口的中位数就是元素本身；k等于n时只有一个窗口；数组中允许出现重复值，删除时必须按「删掉一个副本」而不是「删掉所有等于该值的元素」来处理。
解法：双堆 + 延迟删除
核心思路
每个窗口重新排序需要 $O(k\log k)$，但窗口每次只删除一个数、加入一个数。中位数只依赖有序序列的分界，因此用两个堆维护左右两半：
- 最大堆
small保存较小的一半，堆顶是左半最大值；- 最小堆
large保存较大的一半，堆顶是右半最小值。始终维护三个不变量：
small中的有效元素都不大于large中的有效元素；smallSize == largeSize或smallSize == largeSize + 1；- 读取堆顶前，堆顶一定不是已经离开窗口的元素。
堆不能高效删除内部元素，所以用
delayed[value]记录待删除次数。删除时立即减少对应堆的有效元素数，但只在待删元素到达堆顶时才真正弹出。再平衡必须使用smallSize、largeSize，不能使用包含失效元素的物理堆长度。在上述不变量下，奇数窗口的中位数是
small堆顶；偶数窗口是两个堆顶的平均值。插入、逻辑删除、清理和再平衡都恢复不变量，因此每次得到的都是当前窗口中位数。
解题步骤
- 初始化两个堆、延迟删除计数表，以及两个有效元素计数。
- 插入新值：不大于
small堆顶就进入small，否则进入large，随后再平衡。- 删除旧值：在
delayed中加一，根据它与small堆顶的关系减少对应有效计数；若它正位于堆顶，立即连续清理。- 再平衡：让
small与large有效元素数相等，或让small恰好多一个；搬运后清理原堆新暴露的失效堆顶。- 窗口形成后读取中位数，再继续右移。
例如窗口
[1,3,-1]中，small保存[-1,1]，堆顶为 1，large保存[3]，中位数为 1。窗口右移时 1 离开：先做逻辑删除并减少smallSize；即使它暂时还留在堆数组中，也不会再参与平衡和中位数计算。
代码实现
import java.util.*;
class Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
DualHeap heaps = new DualHeap(k);
for (int i = 0; i < k; i++) {
heaps.insert(nums[i]);
}
double[] ans = new double[nums.length - k + 1];
ans[0] = heaps.median();
for (int right = k; right < nums.length; right++) {
heaps.insert(nums[right]);
heaps.erase(nums[right - k]);
ans[right - k + 1] = heaps.median();
}
return ans;
}
private static class DualHeap {
private final PriorityQueue<Integer> small =
new PriorityQueue<>((a, b) -> Integer.compare(b, a));
private final PriorityQueue<Integer> large = new PriorityQueue<>();
private final Map<Integer, Integer> delayed = new HashMap<>();
private final int windowSize;
private int smallSize;
private int largeSize;
DualHeap(int windowSize) {
this.windowSize = windowSize;
}
void insert(int num) {
if (small.isEmpty() || num <= small.peek()) {
small.offer(num);
smallSize++;
} else {
large.offer(num);
largeSize++;
}
balance();
}
void erase(int num) {
delayed.put(num, delayed.getOrDefault(num, 0) + 1);
if (num <= small.peek()) {
smallSize--;
if (num == small.peek()) {
prune(small);
}
} else {
largeSize--;
if (!large.isEmpty() && num == large.peek()) {
prune(large);
}
}
balance();
}
double median() {
if ((windowSize & 1) == 1) {
return small.peek();
}
return ((long) small.peek() + large.peek()) / 2.0;
}
private void balance() {
if (smallSize > largeSize + 1) {
large.offer(small.poll());
smallSize--;
largeSize++;
prune(small);
} else if (smallSize < largeSize) {
small.offer(large.poll());
smallSize++;
largeSize--;
prune(large);
}
}
private void prune(PriorityQueue<Integer> heap) {
while (!heap.isEmpty()) {
int num = heap.peek();
int count = delayed.getOrDefault(num, 0);
if (count == 0) {
return;
}
heap.poll();
if (count == 1) {
delayed.remove(num);
} else {
delayed.put(num, count - 1);
}
}
}
}
}
import "container/heap"
type intHeap struct {
values []int
max bool
}
func (h intHeap) Len() int { return len(h.values) }
func (h intHeap) Swap(i, j int) { h.values[i], h.values[j] = h.values[j], h.values[i] }
func (h intHeap) Less(i, j int) bool {
if h.max {
return h.values[i] > h.values[j]
}
return h.values[i] < h.values[j]
}
func (h *intHeap) Push(value any) {
h.values = append(h.values, value.(int))
}
func (h *intHeap) Pop() any {
last := len(h.values) - 1
value := h.values[last]
h.values = h.values[:last]
return value
}
func (h intHeap) top() int { return h.values[0] }
type dualHeap struct {
small, large intHeap
delayed map[int]int
windowSize int
smallSize, largeSize int
}
func newDualHeap(windowSize int) *dualHeap {
heaps := &dualHeap{
small: intHeap{max: true},
large: intHeap{},
delayed: make(map[int]int),
windowSize: windowSize,
}
heap.Init(&heaps.small)
heap.Init(&heaps.large)
return heaps
}
func medianSlidingWindow(nums []int, k int) []float64 {
heaps := newDualHeap(k)
for i := 0; i < k; i++ {
heaps.insert(nums[i])
}
ans := make([]float64, 0, len(nums)-k+1)
ans = append(ans, heaps.median())
for right := k; right < len(nums); right++ {
heaps.insert(nums[right])
heaps.erase(nums[right-k])
ans = append(ans, heaps.median())
}
return ans
}
func (h *dualHeap) insert(num int) {
if h.small.Len() == 0 || num <= h.small.top() {
heap.Push(&h.small, num)
h.smallSize++
} else {
heap.Push(&h.large, num)
h.largeSize++
}
h.balance()
}
func (h *dualHeap) erase(num int) {
h.delayed[num]++
if num <= h.small.top() {
h.smallSize--
if num == h.small.top() {
h.prune(&h.small)
}
} else {
h.largeSize--
if h.large.Len() > 0 && num == h.large.top() {
h.prune(&h.large)
}
}
h.balance()
}
func (h *dualHeap) median() float64 {
if h.windowSize%2 == 1 {
return float64(h.small.top())
}
return (float64(h.small.top()) + float64(h.large.top())) / 2
}
func (h *dualHeap) balance() {
if h.smallSize > h.largeSize+1 {
heap.Push(&h.large, heap.Pop(&h.small).(int))
h.smallSize--
h.largeSize++
h.prune(&h.small)
} else if h.smallSize < h.largeSize {
heap.Push(&h.small, heap.Pop(&h.large).(int))
h.smallSize++
h.largeSize--
h.prune(&h.large)
}
}
func (h *dualHeap) prune(target *intHeap) {
for target.Len() > 0 {
num := target.top()
count := h.delayed[num]
if count == 0 {
return
}
heap.Pop(target)
if count == 1 {
delete(h.delayed, num)
} else {
h.delayed[num] = count - 1
}
}
}
复杂度分析
- 时间复杂度：$O(n\log n)$。每个元素入堆一次、最多被物理弹出一次；延迟删除会使物理堆最坏增长到 $O(n)$，所以对数因子按 $\log n$ 计算。
- 空间复杂度：$O(n)$。窗口内有效元素只有 $k$ 个，但尚未浮到堆顶的失效元素最坏可累计到线性规模。
关键点总结
- 两个堆只维护中位数分界，不需要保存完整排序结果。
- 延迟删除把“逻辑失效”和“物理弹出”分开；对外可见的堆顶必须先清理。
- 再平衡看有效计数，不看堆的物理长度。
- 偶数窗口求平均时要先扩宽或转成浮点，避免整型加法溢出。
易错点总结
- 用
heap.size()做平衡：失效但未弹出的元素会干扰大小关系。- 标记删除后不减少有效计数：中位数仍把离窗元素算在内。
delayed使用集合而非计数表：重复值会被一次删掉多个副本。- 搬运堆顶后不调用
prune：新暴露的堆顶可能已经失效。- 两个
int堆顶先相加再转浮点：极值输入可能在转换前溢出。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 295. 数据流的中位数 | 困难 | 只增不删的双堆，无需延迟删除 |
| 剑指 Offer 41. 数据流中的中位数 | 困难 | 同一模型，考察堆的初始化与平均值边界 |
| 面试题 17.20. 连续中值 | 困难 | 换皮题，接口按流式设计 |
| 239. 滑动窗口最大值 | 困难 | 只求极值，单调队列即可，无需维护两半 |
| 4. 寻找两个正序数组的中位数 | 困难 | 输入已有序，改用对分界线二分而非堆 |