Sliding Window Median: медиана скользящего окна на двух кучах и SortedList

Разбор Sliding Window Median (LeetCode 480): две кучи с ленивым удалением по индексу, SortedList, multiset в C++ и дерево Фенвика. Сложность, пример, ошибки и отличия от медианы потока.

12 мин чтенияалгоритмы · кучи · скользящее окно · python

Коротко

ПодходВремя на сдвиг окнаИтогоКогда брать
Сортировать каждое окноO(klog⁡k)O(k \log k)O(nklog⁡k)O(n k \log k)только как отправная точка
Отсортированный список + bisectO(k)O(k)O(nk)O(n k)маленькие kk, быстрый прототип
Две кучи + ленивое удалениеO(log⁡n)O(\log n)O(nlog⁡n)O(n \log n)классический ответ на собеседовании
SortedList / multisetO(log⁡k)O(\log k)O(nlog⁡k)O(n \log k)если библиотека доступна
Фенвик по сжатым значениямO(log⁡n)O(\log n)O(nlog⁡n)O(n \log n)нужен kk-й элемент, а не только медиана
  • Задача — это медиана потока плюс удаление. Именно удаление делает её 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]. Ограничения: 1≤k≤n≤1051 \le k \le n \le 10^5, значения во всём диапазоне 32-битного int.

Чем это отличается от медианы потока

В статье про Find Median from Data Stream числа только приходят. Две кучи держат «разрез» посередине: в max-куче меньшая половина, в min-куче большая. Каждая операция стоит O(log⁡n)O(\log n), медиана читается с вершин за O(1)O(1).

В скользящем окне на каждом шаге одно число приходит, а другое уходит. Уходящее число может лежать где угодно в глубине кучи. Двоичная куча не индексирует элементы по значению, поэтому найти его — O(k)O(k), а это уже не лучше отсортированного списка.

ВопросМедиана потокаМедиана окна
Операциитолько вставкавставка и удаление
Что хранит кучаровно живые элементыживые элементы и ещё не вычищенные мёртвые
Размер для балансировки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

O(nklog⁡k)O(n k \log k). При n=105n = 10^5 и k=5⋅104k = 5 \cdot 10^4 это порядка 101010^{10} операций, не проходит. Зато эта функция пригодится как эталон для стресс-теста.

Следующий шаг — держать окно отсортированным и обновлять через bisect: удалить уходящий элемент и вставить новый. Это O(k)O(k) на шаг из-за сдвига элементов списка. На практике такой код в 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 считает, сколько элементов каждого ранга в окне. Медиана — это kk-й по порядку элемент, а его Фенвик находит спуском по битам за O(log⁡n)O(\log n).

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-й перцентиль окна», «xx-й наименьший». Минус — нужен весь массив заранее, для настоящего потока не подходит. Если значения маленькие (например, от -50 до 50, как в LeetCode 2653 Sliding Subarray Beauty), сжатие не нужно: хватает массива счётчиков и линейного прохода по нему.

Что быстрее на практике

Замер на случайном массиве из 10510^5 чисел в диапазоне 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. Ответ — сумма ∣x−m∣|x - m| по окну, где mm — медиана.

Две кучи справляются с этим почти бесплатно: достаточно поддерживать суммы живых элементов в каждой куче. Мы и так знаем, из какой кучи уходит элемент, так что сумма обновляется вместе со счётчиком. Тогда

cost=m⋅∣low∣−∑low+∑high−m⋅∣high∣.\text{cost} = m \cdot |low| - \sum low + \sum high - m \cdot |high|.

В коде выше это четыре дополнительные строки: low_sum += x при вставке, low_sum -= nums[j] при удалении и перенос v между суммами при перекладывании. С SortedList такое сделать сложнее: сумма префикса в нём не хранится, придётся держать два SortedList — по одному на половину.

Типичные ошибки

  1. Балансировка по len(low). Длина списка включает мусор. Нужны отдельные счётчики живых элементов.
  2. Нет prune после перекладывания. Сняли вершину low, под ней оказался мёртвый элемент, и следующая медиана читает удалённое значение.
  3. Путаница с дубликатами. Со словарём delayed копии одного числа могут лежать в обеих кучах, и при самописной реализации легко уменьшить счётчик не той кучи или сравнить не с той вершиной. Пары (значение, индекс) делают сторону однозначной.
  4. Удаление до вставки без проверки пустоты. При k = 1 окно на мгновение пустеет, и сравнение с low[0] падает с IndexError. Порядок «сначала вставить, потом удалить» эту проблему снимает.
  5. Переполнение при чётном k. В Java и C++ (a + b) / 2 для чисел около 2312^{31} переполняет int. Считайте в long или double.
  6. SortedList.remove по значению, которого нет. Если перепутать индекс уходящего элемента (i - k против i - k + 1), получите ValueError на первом же окне.

Как отвечать на собеседовании

Удобный порядок:

  1. Наивное решение с сортировкой окна — проговорить и сразу оценить.
  2. Отсортированное окно с bisect: O(nk)O(nk), видно, что узкое место — удаление.
  3. Отсылка к медиане потока: «Две кучи решают вставку, осталось удаление».
  4. Ленивое удаление по индексу, отдельные счётчики размеров, prune после каждого изменения вершины.
  5. Сложность O(nlog⁡n)O(n \log n) и честная оговорка про O(n)O(n) памяти под мусор.
  6. Альтернативы одной фразой: SortedList или multiset, Фенвик для произвольного порядкового запроса.

Перед сдачей прогоните стресс-тест против наивного решения на маленьких массивах с повторами: все ошибки этой задачи всплывают на дубликатах и при k = 1. Связанные задачи: Find Median from Data Stream, Median of Two Sorted Arrays, минимум и максимум окна на монотонной очереди и Top K Frequent Elements для практики с кучами.

Потренироваться в спокойной обстановке

Все задачи