企业官网建设流程全解析

LeetCode-Go 题解：480. Sliding Window Median 滑动窗口中位数——双堆与延迟删除实战解析

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

本篇技术指南以 LeetCode-Go 仓库中 0480.Sliding-Window-Median/README.md 为核心，结合仓库内的 Go 源码实现 与 单元测试，系统讲解 LeetCode 480 题「滑动窗口中位数」的两种解法：有序链表模拟法与双堆（大顶堆 + 小顶堆）加延迟删除法。读完本文，你将掌握「动态维护有序数据流中位数」这一经典范式，理解 Go 标准库container/heap的封装技巧，以及解决堆中元素删除问题的通用方案，并能直接复现本仓库的完整代码与测试。

题目描述

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4]，中位数是3

[2,3]，中位数是(2 + 3) / 2 = 2.5

Given an arraynums, there is a sliding window of sizekwhich is moving from the very left of the array to the very right. You can only see theknumbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

例如，给定nums = [1,3,-1,-3,5,3,6,7]，且k = 3：

Window position Median --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6

因此，返回的滑动窗口中位数数组为[1,-1,-1,3,5,6]。

注意：你可以假设k始终合法，即对于非空数组，k总是小于输入数组的长度。

题目大意

中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。

给出一个数组nums，有一个大小为k的窗口从最左端滑动到最右端。窗口中有k个数，每次窗口移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。

解题思路总览

原文档给出了三条解题路径，复杂度差异明显：

需要说明的是：本题在 LeetCode 上属于 Hard 难度，正是因为「滑动窗口」叠加了「中位数维护」两个难点。仓库的website站点的 ChapterTwo/Sliding_Window.md 表格中，也把本题归入 Sliding Window 分类并标记了❤️（值得重点掌握）以及 O(n * log k) / O(k) 的复杂度标注。

另外，原文档明确指出「这一题是第 239 题的升级版」。第 239 题 0239.Sliding-Window-Maximum 只要求窗口内最大值（可用双端队列 O(n) 解决），而本题要求中位数，窗口内"中间元素"的定位决定了其复杂度高于求极值，这也是它成为 Hard 的关键所在。

解法一：有序链表模拟（O(n * K)）

解法一最贴近题意：维护一个始终有序的窗口链表，每次滑动时先移除左端滑出的元素，再按序插入右端新滑入的元素，最后直接取链表中间位置的值作为中位数。源码位于 480. Sliding Window Median.go 的第 10～64 行。

初始化：首窗口排序建链

getWindowList将前k个元素拷贝、排序后依次压入双向链表：

func getWindowList(nums []int, k int) *list.List { s := make([]int, k) copy(s, nums) sort.Ints(s) l := list.New() for _, n := range s { l.PushBack(n) } return l }

滑动：删除 + 有序插入

每次窗口右移一位，需要做两件事：

• removeFromWindow：在链表中找到第一个值等于nums[p1-k]的元素并删除（若找不到则原样返回，保持链表不变）；
• insertInWindow：从表头遍历，把新元素插入到第一个「大于等于它」的元素之前，从而维持链表有序。

func insertInWindow(w *list.List, n int) *list.List { for e := w.Front(); e != nil; e = e.Next() { if e.Value.(int) >= n { w.InsertBefore(n, e) return w } } w.PushBack(n) return w }

取中位数

getMedian先让指针走到链表的第k/2个节点：若k为奇数，该节点即中位数；若k为偶数，中位数为该节点与其前驱节点的平均值。

func getMedian(w *list.List, k int) float64 { e := w.Front() for i := 0; i < k/2; e, i = e.Next(), i+1 { } if k%2 == 1 { return float64(e.Value.(int)) } p := e.Prev() return (float64(e.Value.(int)) + float64(p.Value.(int))) / 2 }

复杂度分析：每次插入 / 删除都需要 O(k) 遍历链表定位，窗口共滑动 n-k+1 次，因此整体时间复杂度 O(n * K)，空间复杂度 O(K)。此解法胜在直观、完全贴合题意，但性能不足以应对大数据量。

解法二：双堆 + 延迟删除（O(n * log k)）

这是本题的标准最优解，也是原文档重点阐述的思路：

• 用两个优先队列（堆）记录窗口内的值；
• 大顶堆（maxH）里的元素都比小顶堆（minH）里的元素小，即小顶堆存放排序后"中间靠后、值偏大"的那一半，大顶堆存放"中间靠前、值偏小"的那一半；
• 若k为偶数，两个堆各放k/2个元素，中位数 = 两个堆顶元素的平均值；
• 若k为奇数，小顶堆比大顶堆多一个元素，中位数 = 小顶堆堆顶元素；
• 删除窗口滑出的元素时，并不真正从堆中物理移除，而是把该元素**标记到对应堆的"删除堆"**中，取top时不断弹出已被标记的元素，保证堆顶始终是有效元素。

底层堆的封装：IntHeap / MinHeap / MaxHeap

源码先用container/heap接口封装了一个基础数组堆IntHeap，再通过内嵌与覆写Less的方式派生出MinHeap和MaxHeap：

type IntHeap struct { data []int } func (h IntHeap) Len() int { return len(h.data) } func (h IntHeap) Swap(i, j int) { h.data[i], h.data[j] = h.data[j], h.data[i] } func (h *IntHeap) Push(x interface{}) { h.data = append(h.data, x.(int)) } func (h *IntHeap) Pop() interface{} { x := h.data[h.Len()-1] h.data = h.data[0 : h.Len()-1] return x } func (h IntHeap) Top() int { return h.data[0] } type MinHeap struct{ IntHeap } func (h MinHeap) Less(i, j int) bool { return h.data[i] < h.data[j] } type MaxHeap struct{ IntHeap } func (h MaxHeap) Less(i, j int) bool { return h.data[i] > h.data[j] }

关键点：Less决定堆序。MinHeap用小顶堆序（<），MaxHeap用大顶堆序（>）；Top()直接取数组首元素data[0]，即堆顶。

可删除堆：MinHeapR / MaxHeapR

延迟删除的核心结构是「真实堆 + 删除标记堆」的组合：

type MinHeapR struct { hp, hpDel MinHeap } func (h MinHeapR) Len() int { return h.hp.Len() - h.hpDel.Len() } func (h *MinHeapR) Top() int { for h.hpDel.Len() > 0 && h.hp.Top() == h.hpDel.Top() { heap.Pop(&h.hp) heap.Pop(&h.hpDel) } return h.hp.Top() } func (h *MinHeapR) Pop() int { x := h.Top() heap.Pop(&h.hp) return x } func (h *MinHeapR) Push(x int) { heap.Push(&h.hp, x) } func (h *MinHeapR) Remove(x int) { heap.Push(&h.hpDel, x) }

要点解读：

1. Len()是"有效长度"：真实堆大小减去已标记删除的元素个数；
2. Remove(x)只是入"删除堆"：O(log k) 完成一次"伪删除"，并不真正调整真实堆结构；
3. Top()负责"清扫"：只要删除堆堆顶与真实堆堆顶相等，就同时弹出这两个堆顶，直到真实堆顶是有效元素。由于大小堆的堆顶分别是最小值 / 最大值，被标记删除的元素只有在"轮到自己当堆顶"时才会被真正清除，这正是延迟删除的精髓；
4. MaxHeapR的实现完全对称，不再赘述。

主流程逐步解析

medianSlidingWindow1一次遍历完成"插入 → 移除 → 再平衡 → 求中位数"四个动作：

func medianSlidingWindow1(nums []int, k int) []float64 { ans := []float64{} minH := MinHeapR{} maxH := MaxHeapR{} for i := range nums { if minH.Len() == 0 || nums[i] >= minH.Top() { minH.Push(nums[i]) } else { maxH.Push(nums[i]) } if i >= k { if nums[i-k] >= minH.Top() { minH.Remove(nums[i-k]) } else { maxH.Remove(nums[i-k]) } } if minH.Len() > maxH.Len()+1 { maxH.Push(minH.Pop()) } else if minH.Len() < maxH.Len() { minH.Push(maxH.Pop()) } if minH.Len()+maxH.Len() == k { if k%2 == 0 { ans = append(ans, float64(minH.Top()+maxH.Top())/2.0) } else { ans = append(ans, float64(minH.Top())) } } } return ans }

逐环节说明：

1. 插入：若小顶堆为空或新元素不小于小顶堆堆顶（即不小于当前"较小的一半"的最大值），则进入小顶堆，否则进入大顶堆。这一步保证大顶堆里所有元素 ≤ 小顶堆里所有元素；
2. 移除：当i >= k时窗口已满，此时nums[i-k]是滑出窗口的元素。判断它原本属于哪一侧（与minH.Top()比较）后，调用对应堆的Remove做延迟删除；
3. 再平衡：保持minH.Len()要么等于maxH.Len()（k 为偶数），要么多 1（k 为奇数），使小顶堆堆顶恰好是窗口内"中间靠右"的元素；
4. 求中位数：仅当两堆有效元素之和等于k（即当前窗口完整）时，按 k 的奇偶输出结果。偶数取(minH.Top() + maxH.Top()) / 2.0（注意转成float64再做浮点除法），奇数直接取minH.Top()。

一个极易踩坑的细节是：minH.Len() + maxH.Len() == k中的Len()是扣除删除标记后的有效长度，因此该判断天然过滤了"窗口尚未填满"的早期阶段。

复杂度分析：每个元素至多入堆、出堆、入删除堆各一次，每次堆操作 O(log k)，总时间复杂度 O(n * log k)；空间上两堆各存 O(k)，整体 O(k)。这正是本仓库在网站表格中标注的复杂度。

测试验证与覆盖细节

仓库为本题编写了覆盖完整的单元测试，见 480. Sliding Window Median_test.go。测试用例精心设计，逐一印证了两种解法的一致性：

测试框架的做法是：对每组用例同时调用链表解法medianSlidingWindow与双堆解法medianSlidingWindow1，先校验输出长度一致，再逐位比对结果，二者互为印证，杜绝了单解法实现偏差。

你可以通过仓库根目录的 gotest.sh 提供的命令验证整个 leetcode 包的覆盖率与正确性：

go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...

或只针对本题快速验证：

go test -v -run Test_Problem480 ./leetcode/0480.Sliding-Window-Median/

注意：本仓库源码位于leetcode包内，测试函数名为Test_Problem480，运行测试时需要以leetcode包为单位执行。

小结

• 暴力法：窗口内每次排序，O(n * K)，仅适用于小数据量；
• 解法一（有序链表）：以 O(n * K) 的代价换来了完全贴合题意的直观实现，是理解题意和验证结果的最佳辅助；
• 解法二（双堆 + 延迟删除）：借助container/heap将插入、删除、取中位数全部压到 O(log k)，整体 O(n * log k) / O(k)，是本题的标准最优解；
• 通用范式：MinHeapR / MaxHeapR这套「真实堆 + 删除标记堆」的延迟删除设计，可复用于任何"滑动窗口 + 有序统计"类题目（如求窗口第 K 大、窗口最频繁元素等），也适用于数据流场景中需要删除过期元素的堆结构问题。

建议读者在阅读本文后，亲手在 源码文件 中走一遍nums = [1,3,-1,-3,5,3,6,7], k = 3的完整推演，并运行测试用例对比两种解法的输出，从而真正掌握双堆维护中位数的核心技巧。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go