---
title: Sliding Window Maximum
difficulty: Hard
category: Sliding Window
leetcode_id: 239
revision_count: 1
last_revision: 2026-09-12
---

# Sliding Window Maximum

> **LeetCode:** [#239](https://leetcode.com/problems/sliding-window-maximum/)
> **Сложность:** Hard
> **Категория:** Sliding Window

## Условие

Дан массив целых чисел `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]
```

## Ключевая идея

Держим очередь индексов `deque` (в Ruby это обычный массив, но с доступом к обоим концам). В очереди два свойства:

1. Индексы идут по возрастанию.
2. Значения `nums` по этим индексам идут **по убыванию**: чем ближе индекс к голове, тем больше его значение.

Значит, в голове очереди всегда лежит индекс максимума текущего окна — читаем максимум за O(1).

Как очередь обновляется при сдвиге окна:

- **Из хвоста выбрасываем индексы со значением не больше нового.** Если в окне уже есть число `x`, а пришло `y >= x`, то `x` больше никогда не станет максимумом: `y` не меньше и уйдёт из окна позже. Держать `x` незачем.
- **Из головы выбрасываем индекс, вышедший из окна.** Окно на шаге `i` — это индексы `[i-k+1, i]`.
- **Новый индекс добавляем в хвост.** Он самый «свежий» и покинет окно позже всех.

## Оценка сложности

- **Время:** O(n). Каждый индекс добавляется в очередь один раз и удаляется не больше одного раза.
- **Память:** O(k). В очереди не больше `k` индексов.

## Решение (Ruby)

```ruby
# @param {Integer[]} nums
# @param {Integer} k
# @return {Integer[]}
def max_sliding_window(nums, k)
  deque = []   # индексы; nums[deque] убывают от головы к хвосту
  result = []

  nums.each_with_index do |num, i|
    # 1. Индекс i-k только что вышел из окна [i-k+1, i]. Если он в голове — убираем.
    deque.shift if deque.first == i - k

    # 2. Из хвоста убираем индексы со значением <= num: новый элемент перекрывает их.
    deque.pop while deque.any? && nums[deque.last] <= num

    # 3. Текущий индекс — в хвост.
    deque << i

    # 4. Голова — максимум окна. Первое полное окно заканчивается на i = k-1.
    result << nums[deque.first] if i >= k - 1
  end

  result
end
```

## Разбор на примере

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

| i | num | шаг 1: голова ушла из окна | шаг 2: хвост ≤ num | deque после шага 3 | максимум окна | result |
|---|-----|----------------------------|--------------------|--------------------|---------------|--------|
| 0 | 1 | – | – | [0] | окно неполное | – |
| 1 | 3 | – | pop 0 (1 ≤ 3) | [1] | окно неполное | – |
| 2 | –1 | – | – | [1, 2] | nums[1] = 3 | [3] |
| 3 | –3 | – | – | [1, 2, 3] | nums[1] = 3 | [3, 3] |
| 4 | 5 | shift 1 (1 == i–k) | pop 3, 2 (–3 ≤ 5, –1 ≤ 5) | [4] | nums[4] = 5 | [3, 3, 5] |
| 5 | 3 | – | – | [4, 5] | nums[4] = 5 | [3, 3, 5, 5] |
| 6 | 6 | – | pop 5, 4 (3 ≤ 6, 5 ≤ 6) | [6] | nums[6] = 6 | [3, 3, 5, 5, 6] |
| 7 | 7 | – | pop 6 (6 ≤ 7) | [7] | nums[7] = 7 | [3, 3, 5, 5, 6, 7] |

Что здесь важно увидеть:

- Индекс 1 (значение 3) держится в очереди шаги 1–3, потому что он максимум для окон, заканчивающихся на i=2 и i=3. На шаге 4 он становится старым и уходит из головы.
- Индексы 2 и 3 (значения –1 и –3) не уходят по возрасту — их вытесняет число 5, потому что они меньше.

## Edge Cases

- **k = 1:** окно из одного элемента — шаг 2 каждый раз выбрасывает предыдущий индекс, результат равен `nums`.
- **k = length:** окно на весь массив — в ответе один глобальный максимум.
- **Массив по убыванию:** новые числа меньше предыдущих, вытеснять из хвоста некого — очередь растёт до `k` и отдаёт свой первый (самый старый) индекс. Результат — первые `n-k+1` элементов массива.
- **Массив по возрастанию:** каждое новое число вытесняет все предыдущие — в очереди всегда один индекс, текущий.
- **Равные значения:** условие `<=` выбрасывает старый равный индекс и оставляет новый (он выйдет из окна позже). Результат от этого не зависит, но очередь короче.
- **Отрицательные числа:** сравнения обычные, никаких особенностей.

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

- **Хранить значения, а не индексы.** Тогда нечем проверить, что максимум ещё внутри окна (шаг 1).
- **Путать границы окна.** Окно на шаге `i` — это `[i-k+1, i]`, поэтому устаревший индекс равен `i-k`. Если написать `deque.first == i - k + 1`, вы выбросите индекс, который ещё в окне, и потеряете максимум.
- **Путать голову и хвост.** Сравнение и `pop` — всегда с хвоста (это правый, «свежий» край). Проверка «вышел из окна» и `shift` — с головы (левый, «старый» край).
- **Строгое `<` вместо `<=` при вытеснении.** Это не ошибка по результату (равные значения дают один и тот же максимум), но в худшем случае (все элементы равны) очередь держит `k` индексов вместо одного. `<=` компактнее.
- **Читать максимум до `i == k-1`.** Пока окно не набрало `k` элементов, ответа ещё нет.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force: пересчитывать максимум в каждом окне | O(n·k) | O(1) | просто, но не пройдёт для больших n |
| Max-heap с ленивым удалением | O(n·log k) | O(k) | максимум на вершине, но вставка и удаление за log k |
| **Очередь с убывающими значениями** | **O(n)** | **O(k)** | **каждый индекс входит и выходит один раз — финальное решение** |
| Sparse Table / Segment Tree | O(n·log n) на построение, O(1)–O(log n) на запрос | O(n·log n) / O(n) | избыточно для скользящего окна |

## Заметки после повторения

_Что забыл? Что пошло не так? На чём застрял? Заполни после каждой тренировки._