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

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

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

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

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

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

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

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

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;
}

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

Самый длинный отрезок с 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
• •непрерывный отрезок, не подпоследовательность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

O(n)

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