---
round: 1
ticket_no: 31
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-12
---

# Билет 31 — Sliding Window Maximum

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

Дан массив `nums` и размер окна `k`. Окно скользит по массиву слева направо по одному элементу. Нужно вернуть максимум для каждого положения окна.

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

Пояснение:
[1  3  -1] -3  5  3  6  7  →  3
 1 [3  -1  -3] 5  3  6  7  →  3
 1  3 [-1  -3  5] 3  6  7  →  5
 1  3  -1 [-3  5  3] 6  7  →  5
 1  3  -1  -3 [5  3  6] 7  →  6
 1  3  -1  -3  5 [3  6  7] →  7
```

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

## Ответ

> Здесь, для того чтобы определять максимальный элемент оперативно, нам нужна куча головой, которая будет являться как раз максимальный элемент. Когда мы сдвигаем окно, мы новый элемент туда докидываем. И это всё равно обеспечивается, что на вершине будет стоять максимальный элемент, выкидывая элементы из кучи. Здесь нужно использовать механизм ленивый. Получается, мы помечаем только элемент, говорим, сколько мы таких элементов выкинули, то есть счётчик, и когда он действительно оказывается на вершине, и мы его сравниваем. В общем, перед сравнением мы должны проверить, не был ли он выкинут. Если был выкинут, мы тогда его выкидываем, перестраиваем в кучу, ещё раз сравниваем. Если ещё раз в ленизе он встречается, тогда ещё раз. Короче, здесь важно корректно ещё ленивое удаление сделать, чтобы это было эффективным.

## Разбор

**Что верно:** max-heap, где максимум окна всегда на вершине, и корректно описанное ленивое удаление (пометить ушедший элемент и вычищать его только при всплытии на вершину) — рабочее решение.

**Что упущено и ошибки:** это не ожидаемое оптимальное: канонический ответ — монотонная deque (убывающая), O(n), и в Ruby она делается обычным массивом без гемов, тогда как для кучи нужна ручная реализация (в stdlib Ruby кучи нет) — лишний риск и время на интервью. Сложность своего варианта (O(n log n)) не названа; граничные случаи (k = 1, k = n, дубликаты) не разобраны.

**Эталонная идея:** deque индексов: с хвоста убираем все nums[idx] <= nums[i], с головы — вышедшие из окна, максимум читаем с головы. Каждый индекс входит и выходит один раз.

**Сложность:** время O(n), память O(k)

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


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