Скользящее окно (переменное)

Скользящее окно (переменное): как это работает?

Окно начинается пустым, оба конца на нулевом индексе. Счётчик или словарь описывает его содержимое.

Правый конец делает шаг и вбирает один элемент. Обновите описание этим элементом.

Проверьте условие на текущем окне. Пока оно выполняется, записывайте ширину или количество.

Когда условие сломалось, шаг делает левый конец. Уберите этот элемент из описания.

Сужайте, пока условие снова не выполнится. Только после этого правый конец идёт дальше.

Ни один конец не шагает назад. Поэтому каждый элемент один раз входит и один раз выходит.

1. окно = aИщем самый длинный отрезок без повторов. Лучшее равно 1.
2. окно = abВходит b, буква новая. Лучшее становится 2.
3. окно = abcВходит c, буква новая. Лучшее становится 3.
4. окно = abcbВходит вторая b. Теперь в окне две буквы b.
5. окно = cbЛевый конец убирает a и первую b. Лучшее остаётся 3.

function longestUnder(arr, limit) {
    let left = 0;
    let sum = 0;
    let best = 0;
    for (let right = 0; right < arr.length; right++) {
        sum += arr[right];
        while (sum > limit) {
            sum -= arr[left];
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

function longestUnder(arr: number[], limit: number): number {
    let left = 0;
    let sum = 0;
    let best = 0;
    for (let right = 0; right < arr.length; right++) {
        sum += arr[right];
        while (sum > limit) {
            sum -= arr[left];
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

def longest_under(arr, limit):
    left = 0
    total = 0
    best = 0
    for right, x in enumerate(arr):
        total += x
        while total > limit:
            total -= arr[left]
            left += 1
        best = max(best, right - left + 1)
    return best

function longestUnder(array $arr, int $limit): int {
    $left = 0;
    $sum = 0;
    $best = 0;
    for ($right = 0; $right < count($arr); $right++) {
        $sum += $arr[$right];
        while ($sum > $limit) {
            $sum -= $arr[$left];
            $left++;
        }
        $best = max($best, $right - $left + 1);
    }
    return $best;
}

    public static int longestUnder(int[] arr, int limit) {
        int left = 0;
        int sum = 0;
        int best = 0;
        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];
            while (sum > limit) {
                sum -= arr[left];
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    public static int LongestUnder(int[] arr, int limit) {
        int left = 0;
        int sum = 0;
        int best = 0;
        for (int right = 0; right < arr.Length; right++) {
            sum += arr[right];
            while (sum > limit) {
                sum -= arr[left];
                left++;
            }
            best = Math.Max(best, right - left + 1);
        }
        return best;
    }

Скользящее окно (переменное): разбор примера

Самый длинный отрезок с k различными символами

Даны строка и число k. Найдите самый длинный отрезок, где не больше k различных символов.

Отрезок должен быть непрерывным, а не разбросанным.

Растите окно вправо и считайте символы в словаре.

Когда ключей стало больше k, сужайте слева, пока их снова не станет достаточно мало. Ширину меряйте после каждого сужения.

function longestKDistinct(s, k) {
    const count = new Map();
    let left = 0;
    let best = 0;

    for (let right = 0; right < s.length; right++) {
        count.set(s[right], (count.get(s[right]) ?? 0) + 1);

        while (count.size > k) {
            const out = s[left];
            count.set(out, count.get(out) - 1);
            if (count.get(out) === 0) count.delete(out); // the key must go, not just the count
            left++;
        }

        best = Math.max(best, right - left + 1);
    }

    return best;
}

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

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

• •самый длинный/короткий непрерывный подмассив или подстрока
• •удовлетворяющий условию (сумма <= K, не более, без нарушения лимита)
• •не более K различных, без повторов, содержит все из X
• •непрерывный отрезок, не подпоследовательность

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

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

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

• Скользящее окно (фиксированный размер) (Sliding window (fixed size)): Фиксированное окно шириной k от первого шага до последнего. Это окно выбирает ширину само.
• Два указателя (с концов) (Two pointers (opposite ends)): Те стартуют врозь на отсортированных данных и сходятся к паре. Здесь оба конца идут в одну сторону.
• Префиксные суммы (Prefix sums): Префиксные суммы работают с отрицательными числами и любыми диапазонами. Сужение же считает, что удаление помогает.
• Хеш-множество / словарь (Hash set / map): Словарь сам по себе описывает всю коллекцию. Окну нужны счётчики только для живого отрезка.

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

• Оставляют в словаре нулевой счётчик

  Размер словаря считает и ключ с нулём. Удаляйте ключ, когда счётчик обнулился.

• Сужают через if вместо while

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

• Берут окно там, где числа отрицательные

  Удаление значения слева может увеличить сумму. Тогда сужение ничего не доказывает.

• Неверно меряют ширину

  Ширина это right минус left плюс один. Без единицы теряется один символ.

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

Паттерн «Скользящее окно (переменное)» решает такие задачи с собеседований: Самая длинная подстрока без повторов, Минимальная длина подмассива с суммой, Подстрока с не более чем k различными символами, Замена повторяющихся символов, Минимальное окно-подстрока, Фрукты в корзины и Максимум подряд идущих единиц III.

• Самая длинная подстрока без повторов: Сужайте, пока повторяющаяся буква не уйдёт.
• Минимальная длина подмассива с суммой: Растите, пока суммы хватает, потом сужайте.
• Подстрока с не более чем k различными символами: Условие окна это размер словаря.
• Замена повторяющихся символов: Ширина минус самый частый счётчик должна остаться меньше k.
• Минимальное окно-подстрока: Растите, пока покрыты все нужные буквы, потом поджимайте.
• Фрукты в корзины: Не более двух видов, та же форма, что и k различных.
• Максимум подряд идущих единиц III: Сужайте, когда в окне стало больше k нулей.

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

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

n до 1e6 и один лучший отрезок дают O(n). Каждый конец сдвигается не более n раз.