--- title: Sliding Window Median difficulty: Hard category: Sliding Window leetcode_id: 480 revision_count: 1 last_revision: 2026-09-12 --- # Sliding Window Median > **LeetCode:** [#480](https://leetcode.com/problems/sliding-window-median/) > **Сложность:** Hard > **Категория:** Sliding Window ## Условие Дан массив целых чисел `nums` и целое `k` — размер окна. Окно движется слева направо по одному элементу. Вернуть массив медиан для каждого положения окна. Медиана чётного окна — среднее арифметическое двух средних элементов. ``` Input: nums = [1,3,-1,-3,5,3,6,7], k = 4 → Output: [0.0,1.0,1.0,3.0,5.0,5.5] Input: nums = [1,2], k = 1 → Output: [1.0,2.0] ``` ## Ключевая идея Две кучи с **ленивым удалением** (lazy deletion): **max-heap** для левой (меньшей) половины окна и **min-heap** для правой (большей). При сдвиге добавляем новый элемент в одну из куч; уходящий элемент помечаем в хеше как удалённый и реально удаляем только когда он всплывает на вершину. Инвариант: `|lo| >= |hi|` и `|lo| - |hi| <= 1`. Медиана: вершина lo (k нечётное) или среднее вершин lo и hi (k чётное). ## Оценка сложности - **Время:** O(n·log k) — каждый элемент входит в кучу и выходит не более одного раза - **Память:** O(k) — две кучи суммарно + хеш для отложенных удалений ## Решение (Ruby) ```ruby # Min-heap (для max-heap используем трюк с -val) class Heap def initialize @a = [] end def push(val) @a << val i = @a.size - 1 while i > 0 p = (i - 1) / 2 break if @a[p] <= @a[i] @a[p], @a[i] = @a[i], @a[p] i = p end end def pop return nil if @a.empty? min = @a[0] last = @a.pop if @a.any? @a[0] = last i = 0 n = @a.size loop do l = 2 * i + 1 r = 2 * i + 2 smallest = i smallest = l if l < n && @a[l] < @a[smallest] smallest = r if r < n && @a[r] < @a[smallest] break if smallest == i @a[i], @a[smallest] = @a[smallest], @a[i] i = smallest end end min end def peek = @a[0] def size = @a.size def any? = @a.any? def empty? = @a.empty? end # @param {Integer[]} nums # @param {Integer} k # @return {Float[]} def median_sliding_window(nums, k) lo = Heap.new # max-heap (храним -val) hi = Heap.new # min-heap (храним +val) lazy = Hash.new(0) # { value => pending_removals } result = [] lo_peek = -> { -lo.peek } lo_push = ->(v) { lo.push(-v) } lo_pop = -> { -lo.pop } # Удаляем лениво отмеченные элементы с вершины кучи clean = lambda do |heap, max_heap: false| while heap.any? raw = heap.peek val = max_heap ? -raw : raw break unless lazy[val] > 0 lazy[val] -= 1 heap.pop end end # Баланс: lo.size >= hi.size и lo.size - hi.size <= 1 balance = lambda do while lo.size < hi.size clean.call(hi) lo_push.call(hi.pop) end while lo.size > hi.size + 1 clean.call(lo, max_heap: true) hi.push(lo_pop.call) end end nums.each_with_index do |num, i| # 1. вставляем новый элемент if lo.empty? || num <= lo_peek.call lo_push.call(num) else hi.push(num) end # 2. лениво удаляем элемент, покинувший окно if i >= k outgoing = nums[i - k] lazy[outgoing] += 1 clean.call(lo, max_heap: true) clean.call(hi) end # 3. балансируем balance.call # 4. записываем медиану if i >= k - 1 clean.call(lo, max_heap: true) if k.odd? result << lo_peek.call.to_f else clean.call(hi) result << (lo_peek.call + hi.peek) / 2.0 end end end result end ``` ## Разбор на примере Проследим на `nums = [1, 3, -1, -3], k = 2`. Ожидаемые медианы: | Окно | Элементы | Sorted | Медиана | |------|----------|--------|---------| | [0..1] | 1, 3 | [1, 3] | (1+3)/2 = 2.0 | | [1..2] | 3, -1 | [-1, 3] | (-1+3)/2 = 1.0 | | [2..3] | -1, -3 | [-3, -1] | (-3+-1)/2 = -2.0 | **Состояние куч после каждого шага:** ``` i num outgoing lo (max-heap внутренне -val) hi (min-heap) lazy median ─ ─── ──────── ───────────────────────────── ───────────── ─── ───── 0 1 – lo=[ ] → push(-1) → [-1] hi=[ ] – 1 3 – [-1] hi=[ ] → push(3) → [3] 2.0 2 -1 1 [-1,1] → clean 1 ✓ → [1] [3] {1⇒1}→{1⇒0} 1.0 3 -3 3 [1,3] [3] → clean 3 ✓ → [] → push(-1) → [-1] -2.0 ↑ balance: pop lo→-1 → hi {3⇒1}→{3⇒0} ``` Ключевые моменты: - **i=2:** outgoing=1 отмечен лениво; при `clean(lo, max: true)` он на вершине (хранится как -1) → реально удалён. - **i=3:** outgoing=3 отмечен; при `clean(hi)` оказывается на вершине → удалён. После этого lo=2, hi=0 — баланс восстанавливается перекладыванием max(lo) → hi. Проверить код можно любым Ruby-рантаймом. Ожидаемый вывод для этого теста: `[2.0, 1.0, -2.0]`. ## Edge Cases - **k = 1:** медиана каждого элемента — он сам; результат `nums.map(&:to_f)`. - **k = len(nums):** одно окно на весь массив — глобальная медиана. - **Все элементы равны:** кучи перекладывают элементы, lazy-счётчики не накапливаются — корректно. - **Чётное k, отрицательные числа:** медиана — `(a + b) / 2.0` (Float). - **Дубликаты:** lazy-счётчик корректно обрабатывает множественные удаления одного значения. ## Типичные ошибки - **Не использовать lazy deletion:** реальное удаление из середины кучи разрушает структуру. - **Не чистить вершины перед медианой:** на вершине может висеть отмеченный к удалению элемент. - **Float vs Integer при чётном k:** `(a + b) / 2.0`, а не `(a + b) / 2`. - **Знак в max-heap:** легко перепутать `peek` и `pop`. `lo_push(-val)`, `lo_pop = -lo.pop`, `lo_peek = -lo.peek`. Всегда трижды проверять знак. - **Баланс после удаления:** даже ленивое удаление может нарушить инвариант `|lo| >= |hi|`. - **Накопление lazy-map:** счётчики не чистятся — это нормально, O(k) амортизировано (каждый элемент входит в lazy ровно один раз). ## Альтернативные подходы | Подход | Время | Память | Комментарий | |--------|-------|--------|-------------| | Brute-force (сортировка каждого окна) | O(n·k·log k) | O(k) | Тривиально, не пройдёт для n~10⁵ | | Sorted array + bsearch_index | O(n·k) | O(k) | Проще в написании, сдвиг O(k) | | **Two heaps + lazy deletion** | **O(n·log k)** | **O(k)** | **Финальное решение** | | Balanced BST (`SortedSet`) | O(n·log k) | O(k) | В Ruby нет встроенного BST | ## Заметки после повторения _Что забыл? Что пошло не так? На чём застрял? Заполни после каждой тренировки._