Sliding Window Median: медиана скользящего окна на двух кучах и SortedList
Разбор Sliding Window Median (LeetCode 480): две кучи с ленивым удалением по индексу, SortedList, multiset в C++ и дерево Фенвика. Сложность, пример, ошибки и отличия от медианы потока.
Коротко
| Подход | Время на сдвиг окна | Итого | Когда брать |
|---|---|---|---|
| Сортировать каждое окно | только как отправная точка | ||
Отсортированный список + bisect | маленькие , быстрый прототип | ||
| Две кучи + ленивое удаление | классический ответ на собеседовании | ||
SortedList / multiset | если библиотека доступна | ||
| Фенвик по сжатым значениям | нужен -й элемент, а не только медиана |
- Задача — это медиана потока плюс удаление. Именно удаление делает её Hard.
- Куча не умеет удалять произвольный элемент, поэтому удаление откладывают: элемент остаётся в куче, пока не всплывёт на вершину.
- Главная ловушка — размеры куч. Физическая длина списка включает «мусор», балансировать нужно по счётчику живых элементов.
Условие
LeetCode 480 (Hard): дан массив nums и число k. Окно длины k сдвигается слева направо на одну позицию. Нужно вернуть медиану каждого окна.
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 окна: [1 3 -1] [3 -1 -3] [-1 -3 5] [-3 5 3] [5 3 6] [3 6 7] ответ: [1, -1, -1, 3, 5, 6]
При чётном k медиана — среднее двух средних элементов: для того же массива и k = 4 ответ [0.0, 1.0, 1.0, 4.0, 5.5]. Ограничения: , значения во всём диапазоне 32-битного int.
Чем это отличается от медианы потока
В статье про Find Median from Data Stream числа только приходят. Две кучи держат «разрез» посередине: в max-куче меньшая половина, в min-куче большая. Каждая операция стоит , медиана читается с вершин за .
В скользящем окне на каждом шаге одно число приходит, а другое уходит. Уходящее число может лежать где угодно в глубине кучи. Двоичная куча не индексирует элементы по значению, поэтому найти его — , а это уже не лучше отсортированного списка.
| Вопрос | Медиана потока | Медиана окна |
|---|---|---|
| Операции | только вставка | вставка и удаление |
| Что хранит куча | ровно живые элементы | живые элементы и ещё не вычищенные мёртвые |
| Размер для балансировки | len(heap) | отдельный счётчик |
| Альтернатива на дереве | не нужна | SortedList, multiset, Фенвик |
Сама механика сдвига окна разобрана в статье про скользящее окно. Здесь окно фиксированной длины, так что указатели двигаются синхронно.
Наивное решение
Отсортировать каждое окно и взять середину:
def median_sliding_window_brute(nums, k): res = [] for i in range(len(nums) - k + 1): w = sorted(nums[i : i + k]) res.append(w[k // 2] if k % 2 else (w[k // 2 - 1] + w[k // 2]) / 2) return res
. При и это порядка операций, не проходит. Зато эта функция пригодится как эталон для стресс-теста.
Следующий шаг — держать окно отсортированным и обновлять через bisect: удалить уходящий элемент и вставить новый. Это на шаг из-за сдвига элементов списка. На практике такой код в Python часто проходит LeetCode, потому что сдвиг выполняется в C через memmove. Но на собеседовании от вас ждут асимптотически лучшего решения.
Две кучи с ленивым удалением
Идея
Возьмём схему медианы потока:
low— max-куча, меньшая половина окна;high— min-куча, большая половина;- инвариант порядка: всё в
lowне больше всего вhigh; - инвариант размера: живых элементов в
lowстолько же, сколько вhigh, или на один больше.
Тогда медиана — вершина low при нечётном k или среднее вершин при чётном.
Удалять уходящий элемент сразу не будем. Только уменьшим счётчик живых элементов той кучи, где он лежит. Физически он останется в куче и будет выброшен, когда окажется на вершине. Нам важно лишь одно: вершины обеих куч всегда живые. Мусор в глубине на медиану не влияет.
Удаление по индексу вместо словаря
В разборе медианы потока ленивое удаление сделано через словарь delayed: «число → сколько копий ждут удаления». Это работает, но с дубликатами легко запутаться: какая из копий числа 3 удалена, а какая живая?
В окне есть способ проще. Будем класть в кучи пары «значение, индекс». Элемент мёртв, если его индекс меньше левой границы окна. Словарь не нужен: проверка idx < left однозначна.
Бонус: пары (значение, индекс) все различны, поэтому порядок становится строгим. Чтобы понять, в какой куче лежит уходящий элемент, достаточно сравнить его пару с вершиной low. Если пара не больше вершины, элемент слева, иначе справа. Дубликаты больше не мешают.
Код
import heapq def median_sliding_window(nums, k): low, high = [], [] # low: (-v, -i) — max-куча; high: (v, i) — min-куча low_size = high_size = 0 # сколько ЖИВЫХ элементов в каждой куче res = [] def prune(left):
# снимаем с вершин элементы, которые уже вышли из окна
while low and -low[0][1] < left:
heapq.heappop(low)
while high and high[0][1] < left:
heapq.heappop(high)
for i, x in enumerate(nums):
# 1. добавляем nums[i]
if low and (x, i) < (-low[0][0], -low[0][1]):
heapq.heappush(low, (-x, -i))
low_size += 1
else:
heapq.heappush(high, (x, i))
high_size += 1
# 2. удаляем nums[i - k]: меняем только счётчик
j = i - k
if j >= 0:
if (nums[j], j) <= (-low[0][0], -low[0][1]):
low_size -= 1
else:
high_size -= 1
prune(j + 1)
# 3. балансировка по живым размерам
while low_size > high_size + 1 or low_size < high_size:
if low_size > high_size + 1:
v, idx = heapq.heappop(low)
heapq.heappush(high, (-v, -idx))
low_size -= 1
high_size += 1
else:
v, idx = heapq.heappop(high)
heapq.heappush(low, (-v, -idx))
low_size += 1
high_size -= 1
prune(j + 1)
# 4. медиана готового окна
if i >= k - 1:
if k % 2:
res.append(-low[0][0])
else:
res.append((-low[0][0] + high[0][0]) / 2)
return res
В `low` лежит `(-v, -i)`: инвертируем оба поля, чтобы вершиной max-кучи была наибольшая пара `(v, i)`. При нечётном `k` функция возвращает `int`; LeetCode принимает такой ответ, а если нужен строго `float`, оберните значение в `float()`.
### Почему это корректно
1. **Вершины живые.** `prune` вызывается после удаления и после каждого перекладывания. Перекладывание снимает вершину, и под ней может оказаться мёртвый элемент — его сразу вычищаем.
2. **Элемент не теряется между кучами.** Мёртвые элементы перекладываются только с вершины, а вершина всегда живая. Значит, каждый мёртвый элемент лежит там, где был в момент смерти, и счётчик мы уменьшили у правильной кучи.
3. **Сравнение с вершиной `low` определяет сторону.** По инварианту порядка всё живое в `low` не больше вершины `low`, всё в `high` больше неё. Уходящий элемент ещё жив в момент сравнения: мы проверяем его до `prune`.
4. **Балансировки хватает одного перекладывания.** До шага разница живых размеров была 0 или 1, вставка и удаление сдвигают её максимум на 2 в любую сторону, а одно перекладывание меняет её ровно на 2. Цикл `while` здесь страховка, а не необходимость.
Случай `low` пустой при удалении невозможен: при `j >= 0` в окне `k + 1 >= 2` живых элемента до удаления, и после прошлой балансировки `low` непуст.
### Разбор на примере
`nums = [1, 3, -1, -3, 5, 3, 6, 7]`, `k = 3`. В таблице содержимое куч после шага. Мёртвые элементы помечены зачёркиванием.
| i | Пришёл | Ушёл | `low` (max) | `high` (min) | Живые | Медиана |
| --- | ------ | ---- | ------------ | ------------ | ----- | ------- |
| 2 | -1 | — | 1, -1 | 3 | 2 / 1 | 1 |
| 3 | -3 | 1 | -1, -3 | 3 | 2 / 1 | -1 |
| 4 | 5 | 3 | -1, -3 | 5 | 2 / 1 | -1 |
| 5 | 3 | -1 | 3, -3 | 5 | 2 / 1 | 3 |
| 6 | 6 | -3 | 5, 3, ~~-3~~ | 6 | 2 / 1 | 5 |
| 7 | 7 | 5 | 6, 3, ~~-3~~ | 7 | 2 / 1 | 6 |
На шаге 3 уходит `1` — вершина `low`, `prune` сразу его выбрасывает. На шаге 4 уходит `3` из `high`, тоже с вершины. А на шаге 6 уходит `-3`, лежащий в глубине `low`: счётчик стал 1, перевес перекладывания исправляют, но сам `-3` остаётся в куче мусором до конца. Медиану он не портит, потому что не на вершине.
### Сложность
Каждый элемент один раз попадает в кучу и не больше одного раза из неё снимается. Перекладываний за шаг — $O(1)$ в амортизированном смысле. Итого $O(n \log n)$ по времени.
Почему $\log n$, а не $\log k$? Мусор может копиться. Пример: окно растёт за счёт больших чисел справа, а из глубины `low` уходят мелкие. Они никогда не всплывут на вершину, и куча разрастается до $O(n)$. Отсюда память $O(n)$ в худшем случае. Если это критично, кучу можно периодически пересобирать: когда мусора стало больше живых элементов, отфильтровать список и вызвать `heapify` за $O(k)$. Амортизированно это даёт $O(\log k)$ на операцию и $O(k)$ памяти.
## SortedList: короче и быстрее
В Python есть библиотека `sortedcontainers`, и её `SortedList` поддерживает вставку, удаление и доступ по индексу за $O(\log k)$ амортизированно. Решение становится тривиальным:
```python
from sortedcontainers import SortedList
def median_sliding_window_sl(nums, k):
window = SortedList(nums[:k])
res = []
for i in range(k, len(nums) + 1):
if k % 2:
res.append(window[k // 2])
else:
res.append((window[k // 2 - 1] + window[k // 2]) / 2)
if i < len(nums):
window.remove(nums[i - k])
window.add(nums[i])
return res
sortedcontainers доступна на LeetCode, но не везде: в некоторых онлайн-IDE на собеседовании и на части олимпиадных платформ её нет. Поэтому договоритесь заранее: «Могу использовать SortedList? Если нет, напишу две кучи».
Внутри SortedList — не дерево, а список отсортированных блоков с индексом над ними. Идейно это ближе к sqrt-декомпозиции, чем к красно-чёрному дереву. Если спросят, как сделать такую структуру самому, можно назвать декартово дерево или skip list с размерами поддеревьев.
То же на C++: multiset и итератор на середину
В C++ std::multiset — сбалансированное дерево. Доступа по индексу нет, но можно держать итератор mid на середину окна и сдвигать его на одну позицию при каждой вставке и удалении:
vector<double> medianSlidingWindow(vector<int>& nums, int k) { multiset<int> window(nums.begin(), nums.begin() + k); auto mid = next(window.begin(), k / 2); // правая из средних vector<double> res; for (int i = k;; i++) { res.push_back(((double)*mid + *prev(mid, 1 - k % 2)) / 2); if (i == (int)nums.size()) return res; window.insert(nums[i]); if (nums[i] < *mid) mid--; // новый элемент встал левее mid if (nums[i - k] <= *mid) mid++; // уходящий левее mid или в нём window.erase(window.lower_bound(nums[i - k])); } }
Тонкость: insert кладёт равный элемент после существующих равных, поэтому при nums[i] == *mid новый элемент правее, и mid не двигаем. А lower_bound удаляет первую из равных копий, которая всегда не правее mid, поэтому mid сдвигаем до удаления. Каст к double до сложения защищает от переполнения int.
Дерево Фенвика: k-й элемент вместо медианы
Если значения можно заранее собрать, есть решение без куч и без библиотек. Сожмём координаты и заведём дерево Фенвика, где tree считает, сколько элементов каждого ранга в окне. Медиана — это -й по порядку элемент, а его Фенвик находит спуском по битам за .
def median_sliding_window_bit(nums, k): vals = sorted(set(nums)) rank = {v: i + 1 for i, v in enumerate(vals)} m = len(vals) tree = [0] * (m + 1) log = 1 << m.bit_length() def update(i, delta): while i <= m: tree[i] += delta i += i & -i def kth(t): # наименьший ранг, у которого префиксная сумма >= t pos = 0 step = log while step: nxt = pos + step if nxt <= m and tree[nxt] < t: pos = nxt t -= tree[nxt] step >>= 1 return vals[pos] # ранг pos + 1 -> индекс pos res = [] for i, x in enumerate(nums): update(rank[x], 1) if i >= k: update(rank[nums[i - k]], -1) if i >= k - 1: if k % 2: res.append(kth(k // 2 + 1)) else: res.append((kth(k // 2) + kth(k // 2 + 1)) / 2) return res
Плюс подхода — он отвечает на любой порядковый запрос, а не только на медиану: «25-й перцентиль окна», «-й наименьший». Минус — нужен весь массив заранее, для настоящего потока не подходит. Если значения маленькие (например, от -50 до 50, как в LeetCode 2653 Sliding Subarray Beauty), сжатие не нужно: хватает массива счётчиков и линейного прохода по нему.
Что быстрее на практике
Замер на случайном массиве из чисел в диапазоне int (CPython, одна машина, порядок величин):
k | Две кучи | SortedList | Фенвик |
|---|---|---|---|
| 3 | ~0.17 с | ~0.07 с | ~0.64 с |
| 1 000 | ~0.30 с | ~0.24 с | ~1.0 с |
| 50 000 | ~0.20 с | ~0.29 с | ~0.66 с |
SortedList и кучи идут вровень. Фенвик проигрывает из-за интерпретатора: два спуска по битам на окно — много операций на Python. На C++ картина другая, там все три варианта укладываются в десятки миллисекунд.
Расширение: стоимость окна
Частый follow-up (есть, например, в задачнике CSES): для каждого окна найти минимальную стоимость сделать все элементы равными, где изменение числа на 1 стоит 1. Ответ — сумма по окну, где — медиана.
Две кучи справляются с этим почти бесплатно: достаточно поддерживать суммы живых элементов в каждой куче. Мы и так знаем, из какой кучи уходит элемент, так что сумма обновляется вместе со счётчиком. Тогда
В коде выше это четыре дополнительные строки: low_sum += x при вставке, low_sum -= nums[j] при удалении и перенос v между суммами при перекладывании. С SortedList такое сделать сложнее: сумма префикса в нём не хранится, придётся держать два SortedList — по одному на половину.
Типичные ошибки
- Балансировка по
len(low). Длина списка включает мусор. Нужны отдельные счётчики живых элементов. - Нет
pruneпосле перекладывания. Сняли вершинуlow, под ней оказался мёртвый элемент, и следующая медиана читает удалённое значение. - Путаница с дубликатами. Со словарём
delayedкопии одного числа могут лежать в обеих кучах, и при самописной реализации легко уменьшить счётчик не той кучи или сравнить не с той вершиной. Пары(значение, индекс)делают сторону однозначной. - Удаление до вставки без проверки пустоты. При
k = 1окно на мгновение пустеет, и сравнение сlow[0]падает сIndexError. Порядок «сначала вставить, потом удалить» эту проблему снимает. - Переполнение при чётном
k. В Java и C++(a + b) / 2для чисел около переполняетint. Считайте вlongилиdouble. SortedList.removeпо значению, которого нет. Если перепутать индекс уходящего элемента (i - kпротивi - k + 1), получитеValueErrorна первом же окне.
Как отвечать на собеседовании
Удобный порядок:
- Наивное решение с сортировкой окна — проговорить и сразу оценить.
- Отсортированное окно с
bisect: , видно, что узкое место — удаление. - Отсылка к медиане потока: «Две кучи решают вставку, осталось удаление».
- Ленивое удаление по индексу, отдельные счётчики размеров,
pruneпосле каждого изменения вершины. - Сложность и честная оговорка про памяти под мусор.
- Альтернативы одной фразой:
SortedListилиmultiset, Фенвик для произвольного порядкового запроса.
Перед сдачей прогоните стресс-тест против наивного решения на маленьких массивах с повторами: все ошибки этой задачи всплывают на дубликатах и при k = 1. Связанные задачи: Find Median from Data Stream, Median of Two Sorted Arrays, минимум и максимум окна на монотонной очереди и Top K Frequent Elements для практики с кучами.