---
round: 3
ticket_no: 10
source_no: 14
slug: sliding-window-median
topic: Sliding Window
difficulty: Hard
leetcode_id: 480
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 10 — Sliding Window Median

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

Дан массив `nums` и целое число `k`. Для каждого окна размером `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 <= nums.length <= 10^5`; `-2^31 <= nums[i] <= 2^31 - 1`.

## Ответ

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

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

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

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

**Разбор задачи:** [`../../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)