480. 滑动窗口中位数
题目描述
输入整数数组 nums 和窗口长度 k。一个长度为 k 的窗口从数组最左侧开始，每次向右挪动一格，直到窗口右端到达数组末尾。
对每个窗口求其中 k 个数的中位数：把这些数排好序，k 为奇数时取正中间那个；k 为偶数时取中间两个数的平均值，例如 [2,3] 的中位数是 2.5。
按窗口从左到右的顺序，返回所有中位数组成的数组。与标准答案相差在 10^-5 以内即视为正确。
示例 1
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[1.0,-1.0,-1.0,3.0,5.0,6.0]
解释：六个窗口依次为 [1,3,-1]、[3,-1,-3]、[-1,-3,5]、[-3,5,3]、[5,3,6]、[3,6,7]，中位数分别是 1、-1、-1、3、5、6。
示例 2
输入：nums = [1,2,3,4,2,3,1,4,2], k = 3 输出：[2.0,3.0,3.0,3.0,2.0,3.0,2.0]
解释：七个窗口排序后的中间值依次为 2、3、3、3、2、3、2。
数据范围
k一定合法，即不超过非空数组nums的长度。- 与真实值误差不超过
10^-5的答案都算正确。
解题思路：有序数组 + 二分插入删除
维护一个始终有序的窗口数组 window。中位数直接读 window[k//2]（偶数时再加上 window[k//2-1] 取平均）。窗口右移时，用二分查找找到离开的数 nums[i-k] 并删除，再用二分查找把新数 nums[i] 插入合适位置。这样不必每次重新排序。
为什么正确
每轮开始时，window 是 nums[i-k .. i-1] 这 k 个数的升序排列。
复杂度分析
时间 O(n·k)：二分查找 O(log k)，但删除和插入要挪动元素 O(k)；空间 O(k)。内存搬移很快，实际可以通过。
易错点
k 为偶数时两个数相加可能超出 32 位整数范围（如 2147483647 + 2147483647），C++/Java 要先转成 long long 或 double 再相加。删除时要删除一个等于 nums[i-k] 的元素，而不是把所有等值元素都删掉。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
window = sorted(nums[:k])
ans = []
for i in range(k, len(nums) + 1):
if k % 2:
ans.append(float(window[k // 2]))
else:
ans.append((window[k // 2 - 1] + window[k // 2]) / 2)
if i == len(nums):
break
window.pop(bisect_left(window, nums[i - k]))
insort(window, nums[i])
return ansclass Solution {
public double[] medianSlidingWindow(int[] nums, int k) {
List<Integer> window = new ArrayList<>();
for (int j = 0; j < k; j++) window.add(nums[j]);
Collections.sort(window);
int n = nums.length;
double[] ans = new double[n - k + 1];
for (int i = k; i <= n; i++) {
if (k % 2 == 1) {
ans[i - k] = window.get(k / 2);
} else {
ans[i - k] = ((double) window.get(k / 2 - 1) + window.get(k / 2)) / 2;
}
if (i == n) {
break;
}
window.remove(lowerBound(window, nums[i - k]));
window.add(lowerBound(window, nums[i]), nums[i]);
}
return ans;
}
private int lowerBound(List<Integer> a, int x) {
int lo = 0, hi = a.size();
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (a.get(mid) < x) lo = mid + 1; else hi = mid;
}
return lo;
}
}class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector<long long> window(nums.begin(), nums.begin() + k);
sort(window.begin(), window.end());
vector<double> ans;
int n = nums.size();
for (int i = k; i <= n; i++) {
if (k % 2) {
ans.push_back((double)window[k / 2]);
} else {
ans.push_back((window[k / 2 - 1] + window[k / 2]) / 2.0);
}
if (i == n) {
break;
}
window.erase(lower_bound(window.begin(), window.end(), (long long)nums[i - k]));
window.insert(upper_bound(window.begin(), window.end(), (long long)nums[i]), nums[i]);
}
return ans;
}
};func medianSlidingWindow(nums []int, k int) []float64 {
window := append([]int{}, nums[:k]...)
sort.Ints(window)
ans := []float64{}
n := len(nums)
for i := k; i <= n; i++ {
if k%2 == 1 {
ans = append(ans, float64(window[k/2]))
} else {
ans = append(ans, (float64(window[k/2-1])+float64(window[k/2]))/2)
}
if i == n {
break
}
p := sort.SearchInts(window, nums[i-k])
window = append(window[:p], window[p+1:]...)
q := sort.SearchInts(window, nums[i])
window = append(window, 0)
copy(window[q+1:], window[q:])
window[q] = nums[i]
}
return ans
}var medianSlidingWindow = function(nums, k) {
const lowerBound = (a, x) => {
let lo = 0, hi = a.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (a[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
};
const window = nums.slice(0, k).sort((a, b) => a - b);
const ans = [];
const n = nums.length;
for (let i = k; i <= n; i++) {
if (k % 2 === 1) {
ans.push(window[k >> 1]);
} else {
ans.push((window[k / 2 - 1] + window[k / 2]) / 2);
}
if (i === n) {
break;
}
window.splice(lowerBound(window, nums[i - k]), 1);
window.splice(lowerBound(window, nums[i]), 0, nums[i]);
}
return ans;
};function medianSlidingWindow(nums: number[], k: number): number[] {
const lowerBound = (a: number[], x: number): number => {
let lo = 0, hi = a.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (a[mid] < x) lo = mid + 1; else hi = mid;
}
return lo;
};
const window = nums.slice(0, k).sort((a, b) => a - b);
const ans: number[] = [];
const n = nums.length;
for (let i = k; i <= n; i++) {
if (k % 2 === 1) {
ans.push(window[k >> 1]);
} else {
ans.push((window[k / 2 - 1] + window[k / 2]) / 2);
}
if (i === n) {
break;
}
window.splice(lowerBound(window, nums[i - k]), 1);
window.splice(lowerBound(window, nums[i]), 0, nums[i]);
}
return ans;
}其他解法
有序数组写法直观，但每次插入删除要移动 O(k) 个元素；双堆加延迟删除把每次操作降到 O(log n)，是“对顶堆”求动态中位数的经典模板。
解法 2：双优先队列 + 延迟删除 时间 O(n log n)，空间 O(n)
用大根堆 small 保存窗口中较小的一半，小根堆 large 保存较大的一半，并让 small 的有效元素比 large 多 0 或 1 个，中位数取自两个堆顶。堆不支持删除任意元素，所以离开窗口的数只记入哈希表 delayed，并调整对应堆的有效计数。每当它出现在堆顶时再真正弹出。每次插入或删除后都重新平衡两个堆。
每次操作是对数级，窗口很大时远快于有序数组的 O(k) 移位。延迟删除要同时维护有效计数和堆顶，细节多，容易写错。
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
small, large = [], [] # small：较小一半（大根堆，存相反数）；large：较大一半（小根堆）
delayed = collections.Counter() # 待删除的数及次数（延迟删除）
size = [0, 0] # 两个堆中有效元素的个数
def prune(h, sign):
# 弹出堆顶所有已标记删除的元素，保证堆顶有效
while h and delayed[sign * h[0]]:
delayed[sign * h[0]] -= 1
heapq.heappop(h)
def balance():
# 保持 small 比 large 多 0 或 1 个有效元素
if size[0] > size[1] + 1:
heapq.heappush(large, -heapq.heappop(small))
size[0] -= 1
size[1] += 1
prune(small, -1)
elif size[0] < size[1]:
heapq.heappush(small, -heapq.heappop(large))
size[0] += 1
size[1] -= 1
prune(large, 1)
def insert(x):
if not small or x <= -small[0]:
heapq.heappush(small, -x)
size[0] += 1
else:
heapq.heappush(large, x)
size[1] += 1
balance()
def erase(x):
delayed[x] += 1
if x <= -small[0]:
size[0] -= 1
if x == -small[0]:
prune(small, -1)
else:
size[1] -= 1
if x == large[0]:
prune(large, 1)
balance()
def median():
return float(-small[0]) if k % 2 else (-small[0] + large[0]) / 2
for x in nums[:k]:
insert(x)
ans = [median()]
for i in range(k, len(nums)):
insert(nums[i])
erase(nums[i - k])
ans.append(median())
return ansclass Solution {
private PriorityQueue<Integer> small = new PriorityQueue<>(Collections.reverseOrder()); // 较小一半
private PriorityQueue<Integer> large = new PriorityQueue<>(); // 较大一半
private Map<Integer, Integer> delayed = new HashMap<>(); // 延迟删除计数
private int smallSize = 0, largeSize = 0;
private void prune(PriorityQueue<Integer> h) {
while (!h.isEmpty() && delayed.containsKey(h.peek())) {
int x = h.poll();
if (delayed.merge(x, -1, Integer::sum) == 0) delayed.remove(x);
}
}
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 insert(int x) {
if (small.isEmpty() || x <= small.peek()) {
small.offer(x);
smallSize++;
} else {
large.offer(x);
largeSize++;
}
balance();
}
private void erase(int x) {
delayed.merge(x, 1, Integer::sum);
if (x <= small.peek()) {
smallSize--;
if (x == small.peek()) prune(small);
} else {
largeSize--;
if (x == large.peek()) prune(large);
}
balance();
}
private double median(int k) {
return k % 2 == 1 ? small.peek() : ((double) small.peek() + large.peek()) / 2;
}
public double[] medianSlidingWindow(int[] nums, int k) {
for (int i = 0; i < k; i++) insert(nums[i]);
double[] ans = new double[nums.length - k + 1];
ans[0] = median(k);
for (int i = k; i < nums.length; i++) {
insert(nums[i]);
erase(nums[i - k]);
ans[i - k + 1] = median(k);
}
return ans;
}
}class Solution {
public:
priority_queue<int> small; // 较小一半，大根堆
priority_queue<int, vector<int>, greater<int>> large; // 较大一半，小根堆
unordered_map<int, int> delayed; // 延迟删除计数
int smallSize = 0, largeSize = 0;
template <typename H>
void prune(H& h) {
while (!h.empty() && delayed.count(h.top())) {
int x = h.top();
if (--delayed[x] == 0) delayed.erase(x);
h.pop();
}
}
void balance() {
if (smallSize > largeSize + 1) {
large.push(small.top());
small.pop();
smallSize--;
largeSize++;
prune(small);
} else if (smallSize < largeSize) {
small.push(large.top());
large.pop();
smallSize++;
largeSize--;
prune(large);
}
}
void insert(int x) {
if (small.empty() || x <= small.top()) {
small.push(x);
smallSize++;
} else {
large.push(x);
largeSize++;
}
balance();
}
void erase(int x) {
delayed[x]++;
if (x <= small.top()) {
smallSize--;
if (x == small.top()) prune(small);
} else {
largeSize--;
if (x == large.top()) prune(large);
}
balance();
}
double median(int k) {
return k % 2 ? small.top() : ((double)small.top() + large.top()) / 2;
}
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
for (int i = 0; i < k; i++) insert(nums[i]);
vector<double> ans{median(k)};
for (int i = k; i < (int)nums.size(); i++) {
insert(nums[i]);
erase(nums[i - k]);
ans.push_back(median(k));
}
return ans;
}
};// 小根堆；较小一半存相反数，从而当作大根堆使用
type medHeap struct{ sort.IntSlice }
func (h *medHeap) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *medHeap) Pop() interface{} {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
func medianSlidingWindow(nums []int, k int) []float64 {
small, large := &medHeap{}, &medHeap{}
delayed := map[int]int{}
smallSize, largeSize := 0, 0
prune := func(h *medHeap, sign int) {
for h.Len() > 0 && delayed[sign*h.IntSlice[0]] > 0 {
delayed[sign*h.IntSlice[0]]--
heap.Pop(h)
}
}
balance := func() {
if smallSize > largeSize+1 {
heap.Push(large, -heap.Pop(small).(int))
smallSize--
largeSize++
prune(small, -1)
} else if smallSize < largeSize {
heap.Push(small, -heap.Pop(large).(int))
smallSize++
largeSize--
prune(large, 1)
}
}
insert := func(x int) {
if small.Len() == 0 || x <= -small.IntSlice[0] {
heap.Push(small, -x)
smallSize++
} else {
heap.Push(large, x)
largeSize++
}
balance()
}
erase := func(x int) {
delayed[x]++
if x <= -small.IntSlice[0] {
smallSize--
if x == -small.IntSlice[0] {
prune(small, -1)
}
} else {
largeSize--
if x == large.IntSlice[0] {
prune(large, 1)
}
}
balance()
}
median := func() float64 {
if k%2 == 1 {
return float64(-small.IntSlice[0])
}
return float64(-small.IntSlice[0]+large.IntSlice[0]) / 2
}
for _, x := range nums[:k] {
insert(x)
}
ans := []float64{median()}
for i := k; i < len(nums); i++ {
insert(nums[i])
erase(nums[i-k])
ans = append(ans, median())
}
return ans
}class Heap {
constructor(less) {
this.a = [];
this.less = less;
}
size() {
return this.a.length;
}
top() {
return this.a[0];
}
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.less(a[i], a[p])) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a;
const top = a[0], last = a.pop();
if (a.length) {
a[0] = last;
let i = 0;
while (true) {
let m = i;
const l = 2 * i + 1, r = l + 1;
if (l < a.length && this.less(a[l], a[m])) m = l;
if (r < a.length && this.less(a[r], a[m])) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
var medianSlidingWindow = function(nums, k) {
const small = new Heap((x, y) => x > y); // 较小一半，大根堆
const large = new Heap((x, y) => x < y); // 较大一半，小根堆
const delayed = new Map(); // 延迟删除计数
let smallSize = 0, largeSize = 0;
const prune = (h) => {
while (h.size() && (delayed.get(h.top()) || 0) > 0) {
delayed.set(h.top(), delayed.get(h.top()) - 1);
h.pop();
}
};
const balance = () => {
if (smallSize > largeSize + 1) {
large.push(small.pop());
smallSize--;
largeSize++;
prune(small);
} else if (smallSize < largeSize) {
small.push(large.pop());
smallSize++;
largeSize--;
prune(large);
}
};
const insert = (x) => {
if (!small.size() || x <= small.top()) {
small.push(x);
smallSize++;
} else {
large.push(x);
largeSize++;
}
balance();
};
const erase = (x) => {
delayed.set(x, (delayed.get(x) || 0) + 1);
if (x <= small.top()) {
smallSize--;
if (x === small.top()) prune(small);
} else {
largeSize--;
if (x === large.top()) prune(large);
}
balance();
};
const median = () => k % 2 ? small.top() : (small.top() + large.top()) / 2;
for (let i = 0; i < k; i++) insert(nums[i]);
const ans = [median()];
for (let i = k; i < nums.length; i++) {
insert(nums[i]);
erase(nums[i - k]);
ans.push(median());
}
return ans;
};class Heap {
a: number[];
less: (x: number, y: number) => boolean;
constructor(less: (x: number, y: number) => boolean) {
this.a = [];
this.less = less;
}
size(): number {
return this.a.length;
}
top(): number {
return this.a[0];
}
push(x: number): void {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (!this.less(a[i], a[p])) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop(): number {
const a = this.a;
const top = a[0], last = a.pop()!;
if (a.length) {
a[0] = last;
let i = 0;
while (true) {
let m = i;
const l = 2 * i + 1, r = l + 1;
if (l < a.length && this.less(a[l], a[m])) m = l;
if (r < a.length && this.less(a[r], a[m])) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
function medianSlidingWindow(nums: number[], k: number): number[] {
const small = new Heap((x, y) => x > y); // 较小一半，大根堆
const large = new Heap((x, y) => x < y); // 较大一半，小根堆
const delayed = new Map<number, number>(); // 延迟删除计数
let smallSize = 0, largeSize = 0;
const prune = (h: Heap): void => {
while (h.size() && (delayed.get(h.top()) || 0) > 0) {
delayed.set(h.top(), delayed.get(h.top())! - 1);
h.pop();
}
};
const balance = (): void => {
if (smallSize > largeSize + 1) {
large.push(small.pop());
smallSize--;
largeSize++;
prune(small);
} else if (smallSize < largeSize) {
small.push(large.pop());
smallSize++;
largeSize--;
prune(large);
}
};
const insert = (x: number): void => {
if (!small.size() || x <= small.top()) {
small.push(x);
smallSize++;
} else {
large.push(x);
largeSize++;
}
balance();
};
const erase = (x: number): void => {
delayed.set(x, (delayed.get(x) || 0) + 1);
if (x <= small.top()) {
smallSize--;
if (x === small.top()) prune(small);
} else {
largeSize--;
if (x === large.top()) prune(large);
}
balance();
};
const median = (): number => k % 2 ? small.top() : (small.top() + large.top()) / 2;
for (let i = 0; i < k; i++) insert(nums[i]);
const ans = [median()];
for (let i = k; i < nums.length; i++) {
insert(nums[i]);
erase(nums[i - k]);
ans.push(median());
}
return ans;
}