Скользящее окно максимума

Скользящее окно максимума

Задача

Дан массив и размер окна k. Требуется найти максимальный элемент в каждом скользящем окне размером k.

Для примера max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3):

• Окно [1, 3, -1] → max = 3
• Окно [3, -1, -3] → max = 3
• Окно [-1, -3, 5] → max = 5
• Окно [-3, 5, 3] → max = 5
• Окно [5, 3, 6] → max = 6
• Окно [3, 6, 7] → max = 7

Результат: [3, 3, 5, 5, 6, 7]

Решение 1: Deque (Оптимальное, O(n))

Используем двусторонюю очередь (deque) для отслеживания полезных элементов.

Ключевая идея: в deque хранить индексы элементов в убывающем порядке значений.

from collections import deque

def max_sliding_window(arr, k):
    """
    Находит максимум в каждом скользящем окне за O(n).
    
    Идея:
    - Deque хранит индексы в убывающем порядке значений
    - Передний элемент deque — индекс максимума
    - Удаляем элементы, вышедшие за границы окна
    - Удаляем элементы меньше текущего (они никогда не будут максимумом)
    """
    if not arr or k <= 0:
        return []
    
    dq = deque()  # Хранит индексы
    result = []
    
    for i in range(len(arr)):
        # Удаляем индексы вне текущего окна
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Удаляем меньшие элементы с конца deque
        # (они никогда не будут максимумом в будущих окнах)
        while dq and arr[dq[-1]] <= arr[i]:
            dq.pop()
        
        # Добавляем текущий элемент
        dq.append(i)
        
        # Когда собрали полное окно, добавляем результат
        if i >= k - 1:
            result.append(arr[dq[0]])
    
    return result

# Тестирование
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
# Вывод: [3, 3, 5, 5, 6, 7]

print(max_sliding_window([1], 1))
# Вывод: [1]

print(max_sliding_window([1, -1], 1))
# Вывод: [1, -1]

Сложность:

• Временная: O(n) — каждый элемент добавляется и удаляется один раз
• Пространственная: O(k) — размер deque не превышает k элементов

Решение 2: Heap (O(n log n))

Проще реализовать, но медленнее.

import heapq

def max_sliding_window_heap(arr, k):
    """
    Использует max-heap. В Python — отрицаемые значения в min-heap.
    Сложность: O(n log n) — не оптимально, но просто.
    """
    if not arr or k <= 0:
        return []
    
    # Python имеет min-heap, используем отрицание для max-heap
    max_heap = []
    result = []
    
    for i in range(len(arr)):
        # Добавляем текущий элемент: (отрицаемое значение, индекс)
        heapq.heappush(max_heap, (-arr[i], i))
        
        # Удаляем элементы вне окна
        while max_heap and max_heap[0][1] <= i - k:
            heapq.heappop(max_heap)
        
        # Когда окно полное
        if i >= k - 1:
            result.append(-max_heap[0][0])
    
    return result

print(max_sliding_window_heap([1, 3, -1, -3, 5, 3, 6, 7], 3))
# Вывод: [3, 3, 5, 5, 6, 7]

Сложность: O(n log n) из-за операций heap

Решение 3: Наивное (O(n*k))

Не рекомендуется, но показывает идею:

def max_sliding_window_naive(arr, k):
    """
    Самое простое решение, но медленное: O(n*k).
    """
    if not arr or k <= 0:
        return []
    
    result = []
    
    for i in range(len(arr) - k + 1):
        window = arr[i:i + k]
        result.append(max(window))
    
    return result

print(max_sliding_window_naive([1, 3, -1, -3, 5, 3, 6, 7], 3))
# Вывод: [3, 3, 5, 5, 6, 7]

Сложность: O(n*k) — слишком медленно

Пошаговое объяснение Deque подхода

Для arr = [1, 3, -1, -3, 5, 3, 6, 7] и k = 3:

i=0: arr[0]=1
  dq = [0]  (никаких результатов ещё)

i=1: arr[1]=3
  arr[1]=3 > arr[0]=1, удаляем 0 с конца
  dq = [1]

i=2: arr[2]=-1
  arr[2]=-1 < arr[1]=3, добавляем 2
  dq = [1, 2]
  РЕЗУЛЬТАТ: arr[1] = 3  ← первое окно

i=3: arr[3]=-3
  Проверяем границу: 0 < 3-3+1=1? Да, удаляем 0 (уже удален)
  arr[3]=-3 < всех, добавляем 3
  dq = [1, 2, 3]
  РЕЗУЛЬТАТ: arr[1] = 3

i=4: arr[4]=5
  Проверяем границу: 1 < 4-3+1=2? Нет
  arr[4]=5 > arr[3]=-3, удаляем 3
  arr[4]=5 > arr[2]=-1, удаляем 2
  arr[4]=5 > arr[1]=3, удаляем 1
  dq = [4]
  РЕЗУЛЬТАТ: arr[4] = 5

i=5: arr[5]=3
  Проверяем границу: 4 < 5-3+1=3? Нет
  arr[5]=3 < arr[4]=5, добавляем 5
  dq = [4, 5]
  РЕЗУЛЬТАТ: arr[4] = 5

i=6: arr[6]=6
  Проверяем границу: 4 < 6-3+1=4? Нет
  arr[6]=6 > arr[5]=3, удаляем 5
  arr[6]=6 > arr[4]=5, удаляем 4
  dq = [6]
  РЕЗУЛЬТАТ: arr[6] = 6

i=7: arr[7]=7
  Проверяем границу: 6 < 7-3+1=5? Нет
  arr[7]=7 > arr[6]=6, удаляем 6
  dq = [7]
  РЕЗУЛЬТАТ: arr[7] = 7

Результат: [3, 3, 5, 5, 6, 7] ✓

Почему Deque оптимален?

1. Ленивое удаление: не пересчитываем максимум каждый раз
2. Монотонная очередь: храним индексы в убывающем порядке значений
3. Оптимальность: каждый элемент обрабатывается ровно 2 раза (добавление и удаление)

Расширения

Минимум вместо максимума:

def min_sliding_window(arr, k):
    if not arr or k <= 0:
        return []
    
    dq = deque()
    result = []
    
    for i in range(len(arr)):
        if dq and dq[0] < i - k + 1:
            dq.popleft()
        
        # Изменяем: ищем минимум (удаляем больших)
        while dq and arr[dq[-1]] >= arr[i]:
            dq.pop()
        
        dq.append(i)
        
        if i >= k - 1:
            result.append(arr[dq[0]])
    
    return result

Sum скользящего окна:

def sliding_window_sum(arr, k):
    """Sum даже проще: O(n) с одной переменной"""
    if not arr or k <= 0:
        return []
    
    result = []
    window_sum = sum(arr[:k])
    result.append(window_sum)
    
    for i in range(k, len(arr)):
        window_sum = window_sum - arr[i - k] + arr[i]
        result.append(window_sum)
    
    return result

Сравнение подходов

Заключение

Deque метод — оптимальное решение для скользящего окна максимума. Ключевые моменты:

1. Храним индексы, а не значения
2. Деque хранит элементы в убывающем порядке
3. Удаляем старые индексы и меньшие элементы
4. Достигаем O(n) временной сложности

Это классический паттерн для задач со скользящим окном, часто встречается на интервью.