round: 4
ticket_no: 06
source_no: 15
slug: sliding-window-maximum
topic: Sliding Window
difficulty: Hard
leetcode_id: 239
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-15
---

# Билет 06 — Sliding Window Maximum

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

Дан массив целых чисел `nums` и целое число `k`. Окно размера `k` сдвигается вправо на один элемент за шаг. Верни массив максимумов для всех положений окна.

```
Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3  →  Output: [3,3,5,5,6,7]
Input:  nums = [1], k = 1                   →  Output: [1]
```

Constraints: `1 <= nums.length <= 10^5`; `-10^4 <= nums[i] <= 10^4`; `1 <= k <= nums.length`.

## Ответ

> Финальная версия из `work-06-sliding-window-maximum.md`:

```ruby
def max_sliding_window(nums, k)
  window = []
  result = []

  nums.each_with_index do |num, i|
    window.shift if !window.empty? && (window.first == i - k)

    while !window.empty? && nums[window.last] <= num
      window.pop
    end

    window.push i
    result.push(nums[window.first]) if i >= k - 1
  end

  result
end

# run O(n)
# mem O(k)
```

## Разбор

**Что верно:**
- Идея — каноническая монотонная deque индексов: с пробела «куча вместо deque» (R1–R3) перешёл на правильную структуру. Инварианты: значения по индексам в deque строго убывают, `first` = максимум окна.
- Три из четырёх шагов цикла верны с первой попытки: `shift` для выкинутого индекса (`window.first == i - k`), `pop` для поддержания монотонности (`nums[window.last] <= num`, с заменой равных на более свежий индекс — правильно), `push`.
- Сложности O(n) (каждый индекс входит/выходит из deque один раз — амортизированно) и O(k) названы верно.
- Финальный код прошёл тесты: классика, k=1, k=2, убывающий/возрастающий массивы, дубликаты, отрицательные — все OK (8/8; единственный отмеченный FAIL в прогоне — ошибка в ожидаемом значении проверяющего, код прав).

**Что упущено и ошибки (итерации пересдачи):**
1. ❌ 1-я версия: `result` никогда не наполнялся — возвращал `[]` (забыт четвёртый шаг: запись максимума).
2. ❌ 2-я версия: `result.push(nums[window.last])` — после `push` это текущий элемент, не максимум; нужен `window.first`.
3. ❌ 3-я версия: отсутствовало `if i >= k - 1` — в ответ попадали «максимумы» неполных окон (лишние k−1 записей в начале).
4. ⚠️ Edge cases в ответе не названы — системный пробел, удержал оценку на 2.

**Эталонная идея:**
Deque индексов с убывающими значениями. Каждый шаг: (1) выкинуть индекс `i-k` из головы; (2) выбросить с хвоста все индексы со значением ≤ текущего (они никогда не станут максимумом); (3) добавить текущий индекс; (4) с `i >= k-1` записать `nums[first]`. Амортизированно O(n).

**Время:** O(n) — каждый индекс max 1 раз push и 1 раз pop.

**Память:** O(k) дополнительная (deque до k индексов) + O(n−k+1) на выход.

**Граничные случаи:** 1) `k = 1` → ответ = nums; 2) `k = nums.length` → одно окно, максимум всего массива; 3) убывающий массив — deque растёт до k, `shift` срабатывает каждый шаг; 4) возрастающий — deque держит 1 индекс, pop каждый шаг; 5) все значения равны — равные заменяются на свежий индекс; 6) отрицательные значения (максимум может быть отрицательным).

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

**Канон сложности:** O(n) / O(k) — совпадает с `complexity-cheat-sheet.md`.

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