跳至主要內容

LeetCode 480. 滑动窗口中位数——双堆+懒删除的高级技巧

老张2026/4/30大约 6 分钟

LeetCode 480. 滑动窗口中位数——双堆+懒删除的高级技巧

适读人群：Java 高级工程师、备战大厂 Hard 题的同学 | 阅读时长：约25分钟 | 难度：困难

开篇故事

上一篇的数据流中位数只需要「加元素」，这道题在此基础上增加了「删元素」——窗口滑动时，旧元素要离开窗口。

堆（PriorityQueue）天然支持高效插入和取堆顶，但删除任意元素需要 O(n) 时间。这个限制让很多同学在这道题上卡住了——往堆里删元素怎么搞？

这就是「懒删除」技巧的用武之地。不立即从堆里删除，而是用一个哈希表记录「待删除」的元素，在堆顶元素恰好是待删除元素时才真正弹出。这个技巧在很多需要「堆 + 删除」的场景里都非常有用，是高级堆操作的标配。

一、题目解析

题目描述：

给你一个数组 nums，有一个大小为 k 的窗口从最左端滑到最右端。每次窗口移动，输出窗口内数字的中位数。

示例：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[1.00,-1.00,-1.00,3.00,5.00,6.00]

二、解法一：暴力排序

每次滑动窗口，对窗口内的 k 个元素排序，取中间值。

import java.util.*;

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] result = new double[n - k + 1];
        int[] window = new int[k];
        
        for (int i = 0; i <= n - k; i++) {
            // 复制窗口元素
            System.arraycopy(nums, i, window, 0, k);
            Arrays.sort(window);
            
            if (k % 2 == 1) {
                result[i] = window[k / 2];
            } else {
                result[i] = ((double) window[k / 2 - 1] + window[k / 2]) / 2;
            }
        }
        
        return result;
    }
}

复杂度： 时间 O(nk log k)，空间 O(k)。

三、解法二：有序集合（TreeMap）

用 TreeMap 维护窗口内的有序多集合，每次插入和删除都是 O(log k)，查询中位数需要找到第 k/2 个元素（需要额外指针维护），整体 O(n log k)。

import java.util.*;

class Solution {
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] result = new double[n - k + 1];
        
        // TreeMap：值 -> 计数，支持重复元素
        TreeMap<Integer, Integer> map = new TreeMap<>();
        
        // 初始化窗口
        for (int i = 0; i < k; i++) {
            map.merge(nums[i], 1, Integer::sum);
        }
        
        // 用 lo 指针维护「中位数左半」
        // 通过维护左半size，动态找中位数
        for (int i = 0; i <= n - k; i++) {
            // 获取中位数
            result[i] = getMedian(map, k);
            
            if (i < n - k) {
                // 加入新元素
                map.merge(nums[i + k], 1, Integer::sum);
                // 删除旧元素
                map.merge(nums[i], -1, Integer::sum);
                if (map.get(nums[i]) == 0) map.remove(nums[i]);
            }
        }
        
        return result;
    }
    
    private double getMedian(TreeMap<Integer, Integer> map, int k) {
        // 找第 (k+1)/2 小和第 (k+2)/2 小的元素
        int target1 = (k + 1) / 2; // 较小的中间位置
        int target2 = (k + 2) / 2; // 较大的中间位置（奇数时与target1相同）
        
        int count = 0;
        int val1 = 0, val2 = 0;
        
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            count += entry.getValue();
            if (val1 == 0 && count >= target1) val1 = entry.getKey();
            if (count >= target2) { val2 = entry.getKey(); break; }
        }
        
        return (val1 + (double) val2) / 2;
    }
}

复杂度： 时间 O(nk)（getMedian 最坏 O(k)），空间 O(k)。

四、解法三（最优）：双堆 + 懒删除

核心思想

在 295「数据流中位数」的双堆基础上，增加懒删除机制来处理窗口滑动时的元素移除。

懒删除原理：

  • 用 HashMap<Integer, Integer> lazy 记录待删除的元素及其数量
  • 每次从堆顶取元素时，检查堆顶是否在 lazy 中（即是否应该被删除）
  • 如果是，就把它真正弹出，并减少 lazy 中的计数
  • 维护「有效大小」（不含待删除元素），用于判断两堆是否平衡

完整代码

import java.util.*;

class Solution {
    // 大根堆：存较小的一半，maxHeap.size() >= minHeap.size()
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    // 小根堆：存较大的一半
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    // 懒删除标记：待删除的元素 -> 待删除次数
    private Map<Integer, Integer> lazy = new HashMap<>();
    // 两堆的有效大小（不含待删除元素）
    private int maxSize = 0, minSize = 0;
    
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        double[] result = new double[n - k + 1];
        
        // 初始化：加入前 k 个元素
        for (int i = 0; i < k; i++) {
            addNum(nums[i]);
        }
        result[0] = findMedian(k);
        
        // 滑动窗口
        for (int i = k; i < n; i++) {
            addNum(nums[i]);      // 加入新元素
            removeNum(nums[i - k]); // 懒删除旧元素
            result[i - k + 1] = findMedian(k);
        }
        
        return result;
    }
    
    private void addNum(int num) {
        // 和295一样的两步插入
        maxHeap.offer(num);
        maxSize++;
        // 平衡值域：把maxHeap的最大值移到minHeap
        minHeap.offer(maxHeap.poll());
        maxSize--;
        minSize++;
        // 平衡大小：maxHeap不能比minHeap小
        if (minSize > maxSize) {
            maxHeap.offer(minHeap.poll());
            minSize--;
            maxSize++;
        }
    }
    
    private void removeNum(int num) {
        lazy.merge(num, 1, Integer::sum); // 标记待删除
        // 判断 num 在哪个堆（通过与 maxHeap 堆顶比较）
        if (!maxHeap.isEmpty() && num <= maxHeap.peek()) {
            maxSize--;
            if (maxHeap.peek().equals(num)) pruneTop(maxHeap);
        } else {
            minSize--;
            if (!minHeap.isEmpty() && minHeap.peek().equals(num)) pruneTop(minHeap);
        }
        // 重新平衡大小
        rebalance();
    }
    
    // 清理堆顶的懒删除元素
    private void pruneTop(PriorityQueue<Integer> heap) {
        while (!heap.isEmpty() && lazy.getOrDefault(heap.peek(), 0) > 0) {
            int top = heap.poll();
            lazy.merge(top, -1, Integer::sum);
            if (lazy.get(top) == 0) lazy.remove(top);
        }
    }
    
    // 平衡两堆大小
    private void rebalance() {
        if (maxSize < minSize) {
            // 从 minHeap 取有效元素到 maxHeap
            pruneTop(minHeap);
            maxHeap.offer(minHeap.poll());
            maxSize++;
            minSize--;
            pruneTop(minHeap);
        } else if (maxSize > minSize + 1) {
            // 从 maxHeap 取有效元素到 minHeap
            pruneTop(maxHeap);
            minHeap.offer(maxHeap.poll());
            minSize++;
            maxSize--;
            pruneTop(maxHeap);
        }
    }
    
    private double findMedian(int k) {
        pruneTop(maxHeap);
        pruneTop(minHeap);
        if (k % 2 == 1) {
            return maxHeap.peek();
        } else {
            return (maxHeap.peek() + (double) minHeap.peek()) / 2;
        }
    }
}

复杂度分析

  • 时间复杂度：O(n log k)。每个元素最多入堆出堆各一次，pruneTop 均摊 O(1)。
  • 空间复杂度：O(n)。懒删除的 HashMap 和堆中可能存有滑出窗口的元素。

五、举一反三

懒删除技巧的适用场景：

题目懒删除的必要性
480. 滑动窗口中位数堆不支持任意位置删除
239. 滑动窗口最大值用单调队列（deque），不需要懒删除
1438. 绝对差不超过限制的最长连续子数组双 TreeMap，直接删除

六、踩坑实录

坑一：removeNum 中对哪个堆减少有效大小的判断

num <= maxHeap.peek() 意味着 num 在大根堆那一侧（较小的一半）。但注意：堆顶可能是懒删除的虚假元素，所以 maxHeap.peek() 不一定是真正有效的堆顶最大值。

这个判断在实践中通常够用，但对于极端情况（堆顶全是懒删除元素），需要先 pruneTop 再比较。

坑二：整型 Integer 用 == 还是 equals

PriorityQueue<Integer> 在取堆顶时返回 Integer 对象，比较时：

  • == 是比较对象引用，对于值 > 127 的 Integer 对象，== 可能返回 false
  • 必须用 .equals(num) 或 intValue() 比较
// 错误：
if (maxHeap.peek() == num) ... // 值超过127时可能不对

// 正确：
if (maxHeap.peek().equals(num)) ...
// 或者明确转型：
if (maxHeap.peek().intValue() == num) ...

坑三：懒删除 HashMap 中要及时清理 value=0 的条目

lazy.merge(top, -1, Integer::sum) 之后，如果 value 变为 0，要 remove 掉，否则后续的 lazy.getOrDefault(top, 0) > 0 判断就会出错。

if (lazy.get(top) == 0) lazy.remove(top); // 及时清理

七、总结

480 是本系列里代码量最大、最容易出 bug 的题之一。核心难点是「懒删除 + 双堆平衡」两个机制的协同工作。

关键点总结：

  1. 懒删除：用 HashMap 标记，堆顶检查时真正清理
  2. 有效大小：maxSize 和 minSize 是排除懒删除后的真实计数
  3. pruneTop：每次需要「读」堆顶前都要先清理懒删除元素
  4. rebalance：删除元素后可能破坏大小平衡，需要重新调整
编辑此页
最近更新:
贡献者: xiaozhangge