---
round: 3
ticket_no: 14
source_no: 15
slug: sliding-window-maximum
topic: Sliding Window
difficulty: Hard
leetcode_id: 239
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 14 — 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]

Пояснение:
[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 <= nums.length <= 10^5`; `-10^4 <= nums[i] <= 10^4`; `1 <= k <= nums.length`.

## Ответ

> Здесь также решение делается через кучу. То есть мы первое окно, когда проходим, первый раз мы заполняем кучу, так что вверху у нас максимальный элемент, вот собственно верхний элемент у нас и является первым значением, то есть мы в результат его отправляем. Дальше, когда мы сдвигаем окно, мы удаляем элемент из кучи, который у нас выходит из окна, и добавляем туда, который в окно попадает. При этом у нас получается удаление должно быть сделано ленивое. То есть это означает, что в моменте оно не удаляется, а помечается, условно говоря, мы говорим, сколько раз мы этот элемент удалили. То есть то, что на самом деле несколько элементов могут храниться одинаковые. И только когда они попадают в голову, при доступе, оно тихо стирается, и это перестраивается структура. Так, дай подумаю, есть ли тут еще какое-то решение. Ну, нет, тут надо использовать эту сортировку, потому что иначе ы окно будем каждый раз пересортировывать. Поэтому здесь важно использовать именно кучу.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

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

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

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