---
round: 1
ticket_no: 32
source_no: 14
slug: sliding-window-median
topic: Sliding Window
difficulty: Hard
leetcode_id: 480
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 32 — Sliding Window Median

## Условие (как предъявлено)

Дан массив `nums` и размер окна `k`. Окно скользит по массиву слева направо по одному элементу. Нужно вернуть медиану для каждого положения окна. Если в окне чётное число элементов, медиана — среднее двух средних значений.

```
Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.0, -1.0, -1.0, 3.0, 5.0, 6.0]
```

Constraints: `1 <= k <= n <= 10^5`, `-2^31 <= nums[i] <= 2^31-1`.

## Ответ

> Здесь нам нужно, когда мы заполняем окно, иметь две кучи: левую и правую. Левая — те, которые меньше, и правая — которые больше. Ну, соответственно, меньшей пирамиды нужно максимальное, чтобы было на вершине. Из большей пирамиды минимальное должно быть на вершине. И получается, что у нас каждый момент времени, когда мы смотрим, у нас чтобы получить медиану, нам нужно сравнить только два вот этих элемента. Вот. Если у нас получается чётные размеры окна, то есть слева и справа кучи одинаковые, значит, мы между ними среднее берём. Если не одинаковые, то мы из большей кучи берём элемент. Это именно он и будет. Вот. И дальше здесь также мы прибавляем новый прибывший элемент. Значит, ну, мы прибавляем его в получается в кучу какую, которая меньше по размеру. Если у нас срабатывает лимит, то мы оттуда... Подожди, лимит какой? Нет. В общем, мы всегда добавляем в кучу большего размера, да. Хорошо. Если они одинаковые, ну значит, а мы должны сравнивать с элементом, который там находится. То есть если у нас... Так, постой, здесь у нас кого-то перестройка кучи должна быть. Ну, во-первых, здесь тоже ленивое удаление предполагается. Что мы только помечаем, чтобы потом, когда он на вершину выскакивает, мы там эффективно это делали. Так, но что касается заполнения, то есть мы выкинули, у нас есть ну размер кучи, мы знаем, да. Для нас важно, чтобы они были сбалансированы. То есть это означает, что если одна из куч начинает по размеру быть больше другой, мы должны оттуда элемент вытащить и вставить его в другую кучу, вот так сбалнсировать, чтобы у них была разница максимум в один элемент.

## Разбор

**Что верно:** две кучи — max-heap для левой половины, min-heap для правой, медиана из вершин, балансировка размеров с разницей не больше одного, ленивое удаление — эталонный подход к самой сложной задаче раунда.

**Что упущено и ошибки:** правило вставки не доведено (идёт в левую кучу, если значение <= lo.top, иначе в правую, затем ребаланс) — в ответе было «прибавляем в кучу большего размера… постой»; не названа сложность O(n log k) / O(k); не проговорены чётность k, формат float и граничные случаи (k = 1, k = n, дубликаты).

**Эталонная идея:** lo = MaxHeap, hi = MinHeap, hash отложенных удалений; вставка и ребаланс; медиана = lo.top или (lo.top + hi.top) / 2.0.

**Сложность:** время O(n log k), память O(k)

**Критерии:** идея ✅ · структура данных ✅ · сложность ❌ · граничные случаи ⚠️


**Разбор задачи:** [`../../algo-solutions/01-must-have/05-sliding-window/14-sliding-window-median.md`](../../algo-solutions/01-must-have/05-sliding-window/14-sliding-window-median.md)