Скользящее окно (фиксированный размер)

Скользящее окно (фиксированный размер): как это работает?

Соберите первое окно из первых k элементов. Ответ для него посчитайте один раз, напрямую.

Теперь сдвиньте окно на одну ячейку вправо. Ровно один элемент входит и один выходит.

Обновите текущее значение по этим двум элементам. Прибавьте вошедший и вычтите вышедший.

Запишите ответ для этого окна до следующего сдвига. Лучший результат живёт в одной переменной.

Повторяйте, пока правый край не дойдёт до конца. Всего окон n минус k плюс один.

Ни одно окно не считается заново целиком. Именно это превращает O(nk) в O(n).

Источники: Википедия: Скользящая средняя

1. [4, 2, 7] сумма = 13Размер окна равен трём. Первое окно суммируется напрямую.
2. [2, 7, 1] сумма = 10Входит 1, выходит 4. Значит 13 плюс 1 минус 4 это 10.
3. лучшее = 13Это окно хуже первого. Лучший результат не меняется.
4. [7, 1, 5] сумма = 13Входит 5, выходит 2. Значит 10 плюс 5 минус 2 это 13.
5. ответ = 13Правый край дошёл до конца. Три окна, пять чтений.

function windowStat(arr, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += arr[i];
    let best = windowSum;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

function windowStat(arr: number[], k: number): number {
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += arr[i];
    let best = windowSum;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

def window_stat(arr, k):
    window_sum = sum(arr[:k])
    best = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        best = max(best, window_sum)
    return best

function windowStat(array $arr, int $k): int {
    $windowSum = array_sum(array_slice($arr, 0, $k));
    $best = $windowSum;
    for ($i = $k; $i < count($arr); $i++) {
        $windowSum += $arr[$i] - $arr[$i - $k];
        $best = max($best, $windowSum);
    }
    return $best;
}

    public static int windowStat(int[] arr, int k) {
        int windowSum = 0;
        for (int i = 0; i < k; i++) windowSum += arr[i];
        int best = windowSum;
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k];
            best = Math.max(best, windowSum);
        }
        return best;
    }

    public static int WindowStat(int[] arr, int k) {
        int windowSum = 0;
        for (int i = 0; i < k; i++) windowSum += arr[i];
        int best = windowSum;
        for (int i = k; i < arr.Length; i++) {
            windowSum += arr[i] - arr[i - k];
            best = Math.Max(best, windowSum);
        }
        return best;
    }

Скользящее окно (фиксированный размер): разбор примера

Найти все анаграммы слова

Даны строка s и более короткая строка p. Верните все начальные индексы, где в s стоит анаграмма p.

Анаграмма использует те же буквы в тех же количествах.

Посчитайте буквы p один раз. Потом катите окно такой же длины по строке s.

Каждый сдвиг добавляет одну букву и убирает одну. Сравните счётчики и при совпадении запишите индекс.

function findAnagrams(s, p) {
    if (p.length > s.length) return [];

    const need = new Array(26).fill(0);
    const have = new Array(26).fill(0);
    const at = (c) => c.charCodeAt(0) - 97;

    for (const c of p) need[at(c)]++;

    const result = [];
    for (let i = 0; i < s.length; i++) {
        have[at(s[i])]++;

        // one letter leaves as soon as the window is longer than p
        if (i >= p.length) have[at(s[i - p.length])]--;

        if (i >= p.length - 1 && need.every((n, j) => n === have[j])) {
            result.push(i - p.length + 1);
        }
    }

    return result;
}

Скользящее окно (фиксированный размер): когда применять?

Паттерн «Скользящее окно (фиксированный размер)» нужен, когда в условии есть слова «непрерывный подмассив/подстрока заданной длины k», «каждое окно размера k» или «скользящее среднее или скользящая сумма». Решение на нём обычно укладывается в O(n).

• •непрерывный подмассив/подстрока заданной длины k
• •каждое окно размера k
• •скользящее среднее или скользящая сумма
• •мин/макс/количество/сумма по каждому фиксированному отрезку

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Скользящее окно (фиксированный размер): с чем путают?

Паттерн «Скользящее окно (фиксированный размер)» чаще всего путают с этими паттернами: Скользящее окно (переменное), Префиксные суммы, Монотонная дек-очередь (максимум/минимум окна) и Хеш-множество / словарь.

• Скользящее окно (переменное) (Sliding window (variable)): Переменное окно само выбирает ширину по условию. Это окно на всём проходе шириной k.
• Префиксные суммы (Prefix sums): Префиксные суммы строятся один раз и отвечают про любой диапазон. Окно отвечает про один движущийся отрезок.
• Монотонная дек-очередь (максимум/минимум окна) (Monotonic deque (sliding window max/min)): Сумма переживает вычитание, поэтому хватает арифметики. Максимуму нужна дек-очередь.
• Хеш-множество / словарь (Hash set / map): Словарь считает по всей коллекции и не знает позиций. Окно спрашивает только про k соседей.

Скользящее окно (фиксированный размер): частые ошибки

• Пересобирают окно на каждом шаге

  Суммирование k элементов в каждой позиции стоит O(nk). Используйте прошлый итог.

• Записывают ответ слишком рано

  Первые k минус одна позиций держат неполное окно. Начинайте запись, когда оно заполнилось.

• Убирают не тот элемент

  Выходящее значение стоит на индексе i минус k. Ошибка на единицу сдвигает все окна.

• Берут скользящую сумму ради максимума

  Вычитание вышедшего элемента максимум не восстановит. Для этого случая нужна монотонная дек-очередь.

Скользящее окно (фиксированный размер): задачи с собеседований

Паттерн «Скользящее окно (фиксированный размер)» решает такие задачи с собеседований: Максимальная сумма подмассива длины k, Максимальное среднее подмассива I, Все анаграммы в строке, Перестановка в строке, Повторяющиеся последовательности ДНК, Максимум скользящего окна и Средние в радиусе k.

• Максимальная сумма подмассива длины k: Базовая форма: одно сложение и одно вычитание за шаг.
• Максимальное среднее подмассива I: Та же сумма, делённая на k в конце.
• Все анаграммы в строке: Окно несёт счётчики букв вместо суммы.
• Перестановка в строке: Те же счётчики, но останов на первом совпадении.
• Повторяющиеся последовательности ДНК: Каждое окно из десяти символов, подсчёт в словаре.
• Максимум скользящего окна: Фиксированное окно, чей ответ требует монотонной дек-очереди.
• Средние в радиусе k: Окно центрируется на индексе, а не тянется за ним.

Скользящее окно (фиксированный размер): сложность по времени и памяти

У паттерна «Скользящее окно (фиксированный размер)» целевая сложность O(n).

n до 1e6 при окне размера k даёт O(n). Каждый элемент один раз входит в окно и один раз выходит.