LeetCode 480. 滑动窗口中位数
题目描述
题意分析
长度为
k的窗口从数组最左端开始，每次向右移动一格，按窗口出现顺序返回每个窗口的中位数。中位数按窗口元素的有序位置定义：奇数长度取正中间的值，偶数长度取中间两个值的平均数。每次移动只加入一个新值、移出一个旧值。相同值的多次出现属于不同元素，移出时只减少一次；答案共有
n - k + 1个，可能带小数。题目保证1 <= k <= n，元素可以覆盖完整 32 位有符号整数范围。
解法：双堆 + 延迟删除
核心思路
[!blue]
若每个窗口重新排序，会反复处理大部分相同元素。用两个堆维护有序划分：大根堆
small保存较小的一半，小根堆large保存较大的一半，所有有效小半区元素都不大于有效大半区元素。有效数量保持相等，或small恰好多一个，这样奇数窗口的中位数就是small堆顶，偶数窗口则取两个堆顶的平均数。插入新值时，以有效的
small堆顶为分界，较小或相等的值进入small，更大的值进入large。若一侧有效数量过多，将它的边界元素搬到另一侧：小半区过多时搬最大值，大半区过多时搬最小值，既调整数量，也维持两侧的大小关系。普通堆能高效弹出堆顶，但不能快速找到内部任意旧元素。于是移出值时不立即搜索堆数组，而是在
delayed[value]中登记待删除次数，同时立刻减少所属半区的有效数量。值不大于small堆顶时归小半区，否则归大半区；分界处存在相同值时，可以将任意一次等值出现视作被删除者，因为它们在中位数计算中可以互换。
smallSize、largeSize表示当前真正参与排序的数量，物理堆中还可能埋着已过期元素，两者不能混用。prune只检查堆顶：若这个值有待删除次数，就弹出一次并消耗一次额度，直到堆顶有效。删除已经在登记时扣过有效数量，所以这里不能重复扣减。堆顶的有效性也需要维护：被删值等于当前堆顶时立即清理；平衡时搬走堆顶后，再清理新暴露的堆顶。这样下一次划分、搬移以及读取中位数使用的都是有效值。过期值仍埋在内部时不影响堆顶，只需等它以后露出再处理。
初始化先加入前
k个值并输出一次；之后每次先加入新值，再登记并删除旧值，两个操作各自完成平衡，恢复到k个有效元素后再输出。偶数窗口相加前先转换为宽整数或浮点，避免两个合法整数相加时先溢出。
解题步骤
- 建立小半区大根堆、大半区小根堆、待删次数表，以及两个有效数量计数器。
- 插入前
k个值，每次按堆顶分界插入并平衡，随后读取第一个中位数。- 窗口右移时先插入新值，再为离开的值登记一次待删除，并减少所属半区的有效数量。
- 删除命中堆顶时立即清理；按有效数量搬移堆顶恢复平衡，并清理搬移后新暴露的过期项。
- 依据窗口奇偶读取中位数。重复直到全部窗口处理完成，按顺序返回结果。
代码实现
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)$，埋在堆中的过期项不保证及时移除，不能直接写成 $O(k)$。
关键点总结
[!green]
- 有序划分决定两个堆顶是中间位置，数量平衡决定奇偶窗口应该读取哪一项。
- 延迟表记录待删次数，有效数量立即减少，物理删除只在堆顶兑现，两种记账不能重复。
- 重复值按出现次数删除，堆顶与其他副本等值时可以互换，不需要追踪原下标。
- 过期项可能长期留在物理堆中，本实现的堆大小不能按窗口大小
k保证。
易错点总结
[!yellow]
- 用物理堆长度做平衡，会把过期项继续当成窗口成员；应使用
smallSize、largeSize。prune时再次减少有效数量，会对同一次删除重复记账。- 待删表只存布尔值无法表达多个相同旧值，必须累积并逐次消耗次数。
- 搬走堆顶后不清理新堆顶，可能把过期值用于下次分界或中位数。
- 偶数窗口先用整数相加再转浮点，可能在转换前就溢出，应先转换操作数。
- 物理堆存在延迟清理，不能直接承诺
O(k)空间或按堆大小k推导时间上界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 295. 数据流的中位数 | 困难 | 双堆的有序划分与平衡规则相同，本题还需要处理离开窗口的旧元素。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！