Скользящее окно

Что такое подмассивы?

Прежде чем перейти к этой теме нужно четко понимать, что такое подстрока и подмассив - substring and subarray.

Например, для массива [1, 2, 3, 4] мы будем иметь следующие подмассивы:

Одиночные - [1], [2], [3], [4]
Двойные - [1, 2], [2, 3], [3, 4]
Тройные - [1, 2, 3], [2, 3, 4]
Четверные - [1, 2, 3, 4]

Формула для расчета количества подстрок и подмассивов:

Пример кода

const findAllSubarrays = (arr) => {
  const subarrays = [];
  for (let start = 0; start < arr.length; start++) {
    for (let end = start; end < arr.length; end++) {
      subarrays.push(arr.slice(start, end + 1));
    }
  }
  return subarrays;
};

const arr = [1, 2, 3];
console.log(findAllSubarrays(arr)); // Вывод: [[1], [1, 2], [1, 2, 3], [2], [2, 3], [3]]

В примере ниже - подмассив это непрерывная часть массива ограниченная двумя пойнтерами. Но так как это уже окно, то давайте их называть левый край окна и правый край окна.

В каких задачах нужно такое решение?

Существует очень распространенная группа задач, связанных с подмассивами, которые можно эффективно решать с помощью скользящего окна. Давайте обсудим, как идентифицировать эти задачи.
Во-первых, проблема будет явно или неявно определять критерии, которые делают подмассив "валидным".

Есть два компонента, которые определяют, что делает подмассив валидным:

• Метрическая ограниченность. Это некоторая характеристика подмассива. Это может быть сумма, количество уникальных элементов, частота определенного элемента или любая другая характеристика.
• Числовое ограничение на метрическую ограниченность. Это то, какой должна быть метрическая ограниченность, чтобы подмассив считался валидным.

Например, допустим, что в задаче указано, что подмассив является валидным, если его сумма меньше или равна 10. Метрическая ограниченность здесь - это сумма подмассива, а числовое ограничение - <= 10. Подмассив считается валидным, если его метрическая ограниченность соответствует числовому ограничению, то есть сумма меньше или равна 10.

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

Вот предварительный просмотр некоторых примеров задач, чтобы помочь вам лучше понять, как выглядят задачи с использованием скользящего окна:

• Найдите самый длинный подмассив с суммой, меньше или равной k.
• Найдите самую длинную подстроку, в которой не более одной "0".
• Найдите количество подмассивов, у которых произведение меньше k.

Алгоритм

Идея скользящего окна заключается в рассмотрении только валидных подмассивов. Напомним, что подмассив может быть определен левым ограничением (индекс первого элемента) и правым ограничением (индекс последнего элемента). В скользящем окне мы поддерживаем две переменные left и right, которые в любой момент времени представляют текущий рассматриваемый подмассив.

Изначально у нас left = right = 0, что означает, что первый подмассив, который мы рассматриваем, состоит только из первого элемента массива. Мы хотим расширить размер нашего "окна", и мы делаем это, увеличивая right. Когда мы увеличиваем right, это похоже на "добавление" нового элемента в наше окно.

Но что, если после добавления нового элемента подмассив становится невалидным? Нам нужно "удалить" некоторые элементы из нашего окна, пока оно снова не станет валидным. Чтобы "удалить" элементы, мы можем увеличить left, что уменьшает размер нашего окна.

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

Чтобы объяснить, почему этот алгоритм работает, давайте рассмотрим конкретный пример.

Допустим, нам дан положительный целочисленный массив nums и целое число k. Нам нужно найти длину самого длинного подмассива, сумма которого меньше или равна k. В этом примере пусть nums = [3, 2, 1, 3, 1, 1] и k = 5.

Изначально у нас left = right = 0, поэтому наше окно содержит только первый элемент: [3]. Теперь давайте расширим окно вправо, пока не будет нарушено ограничение. Это произойдет, когда left = 0, right = 2, и наше окно будет: [3, 2, 1]. Сумма здесь равна 6, что больше k. Теперь мы должны уменьшить окно слева, пока ограничение не перестанет нарушаться. После удаления одного элемента окно снова становится валидным: [2, 1].

Почему правильно удалить этот 3 и забыть о нем до конца алгоритма? Потому что входные данные содержат только положительные целые числа, более длинный подмассив напрямую равен большей сумме. Мы знаем, что [3, 2, 1] уже приводит к слишком большой сумме. Нет никакого способа снова получить валидное окно, если мы оставим этот 3, потому что если мы добавим еще элементы справа, сумма только увеличится. Поэтому мы можем забыть о 3 до конца алгоритма.

Реализация

Теперь, когда у вас есть представление о том, как работает скользящее окно, давайте поговорим о том, как его реализовать. В этом разделе мы будем использовать предыдущий пример (найти самый длинный подмассив с суммой, меньше или равной k).

Как описано выше, нам нужно определить метрическую ограниченность. В нашем примере метрическая ограниченность - это сумма окна. Как мы можем отслеживать сумму окна по мере добавления и удаления элементов? Один из способов сделать это - хранить окно в отдельном массиве. Когда мы добавляем элементы справа, мы добавляем их в наш массив. Когда мы удаляем элементы слева, мы удаляем соответствующие элементы из массива. Таким образом, мы всегда можем найти сумму нашего текущего окна, просто суммируя элементы в отдельном массиве.

Это очень неэффективно, так как удаление элементов и нахождение суммы окна будут операциями 𝑂(𝑛). Как мы можем улучшить?

Нам на самом деле не нужно хранить окно в отдельном массиве. Все, что нам нужно, это некоторая переменная, назовем ее curr, которая отслеживает текущую сумму. Когда мы добавляем новый элемент справа, мы просто делаем curr += nums[right]. Когда мы удаляем элемент слева, мы просто делаем curr -= nums[left]. Таким образом, все операции выполняются за 𝑂(1).

Далее, как мы перемещаем указатели left и right? Помните, что мы хотим продолжать расширять наше окно, и окно всегда скользит вправо - оно может только сжиматься несколько раз по пути. Поскольку right всегда движется вперед, мы можем использовать цикл for, чтобы итерировать right по входным данным. В каждой итерации цикла for мы будем добавлять элемент nums[right] в наше окно.

Что насчет left? Когда мы перемещаем left, мы сжимаем наше окно. Мы сжимаем окно только тогда, когда оно становится невалидным. Поддерживая curr, мы можем легко определить, является ли текущее окно валидным, проверяя условие curr <= k. Когда мы добавляем новый элемент и окно становится невалидным, нам может потребоваться удалить несколько элементов слева. Например, пусть nums = [1, 1, 1, 3] и k = 3. Когда мы дойдем до 3 и добавим его в окно, окно станет невалидным. Нам нужно удалить три элемента слева, прежде чем окно снова станет валидным.

Это предполагает, что мы должны использовать цикл while для выполнения удалений. Условие будет while (curr > k) (пока окно невалидно). Для выполнения удалений мы делаем curr -= nums[left] и затем увеличиваем left в каждой итерации цикла while.

Наконец, как мы обновляем ответ? В каждой итерации цикла for, после цикла while, текущее окно валидно. Мы можем написать код здесь, чтобы обновить ответ. Формула для длины окна - right - left + 1.

Вот псевдокод, который объединяет все вместе:

function fn(nums, k):
    left = 0
    curr = 0
    answer = 0
    for (int right = 0; right < nums.length; right++):
        curr += nums[right]
        while (curr > k):
            curr -= nums[left]
            left++

        answer = max(answer, right - left + 1)

    return answer

Почему скользящее окно эффективно?

Для любого массива, сколько существует подмассивов? Если длина массива равна n, то существует n подмассивов длиной 1. Затем существует n - 1 подмассивов длиной 2 (каждый индекс, кроме последнего, может быть начальным индексом), n - 2 подмассивов длиной 3 и так далее, пока не останется только 1 подмассив длиной n. Это означает, что существует

подмассивов (это частичная сумма этой серии). С точки зрения временной сложности, любой алгоритм, который рассматривает каждый подмассив, будет иметь сложность не менее O(n^2), что обычно слишком медленно. Скользящее окно гарантирует максимум 2n итераций окна - правый указатель может перемещаться n раз, и левый указатель может перемещаться n раз. Это означает, что если логика, выполняемая для каждого окна, имеет сложность O(1), алгоритмы скользящего окна работают за O(n), что значительно быстрее.

Вы можете подумать: внутри цикла for есть цикл while, разве временная сложность не O(n^2)? Причина, по которой это все еще O(n), заключается в том, что цикл while может выполняться только n раз в общей сложности для всего алгоритма (левый указатель начинает с 0, только увеличивается и никогда не превышает n). Если бы цикл while выполнялся n раз в одной итерации цикла for, это означало бы, что он вообще не выполнялся бы для всех остальных итераций цикла for. Это то, что мы называем амортизированным анализом - даже если в худшем случае итерация внутри цикла for имеет сложность O(n), в среднем это O(1), если учитывать все время выполнения алгоритма.

Ничего не понял, хочу узнать больше деталей

Почему временная сложность остается O(n), несмотря на вложенный цикл while?
Вы можете подумать: если внутри цикла for есть еще один цикл while, разве это не делает временную сложность O(n^2) (квадратичной)? Вот почему это не так:

Пример

Представьте, что у нас есть лента на конвейере, и два человека стоят с левой и правой сторон этой ленты. Лента представляет собой массив чисел.

Правый человек (right) двигается вдоль ленты, проверяя каждый элемент.
Левый человек (left) иногда тоже двигается, но только тогда, когда это необходимо.

Как это работает

• Инициализация: Оба человека начинают на одном и том же месте — в начале ленты.
• Движение правого человека: Правый человек (right) двигается по ленте от начала до конца. Это цикл for.
• Движение левого человека: Левый человек (left) двигается только тогда, когда нужно "исправить" ситуацию, чтобы лента снова была в допустимом состоянии. Это цикл while.

Важный момент

• Общее количество шагов: Левый человек (left) за весь процесс пройдет вдоль ленты максимум n шагов, потому что он только двигается вперед и никогда не возвращается назад.
• Амортизированный анализ: Если в какой-то момент левому человеку приходится пройти много шагов, то это означает, что в других моментах ему не нужно будет двигаться вообще. В среднем, каждый его шаг распределяется равномерно по всему времени выполнения алгоритма.

Пример с лентой

Представьте, что правый человек (right) проходит по ленте длиной 10 элементов:

• На первых нескольких шагах левому человеку (left) не нужно двигаться вообще.
• В какой-то момент правый человек (right) доходит до элемента, который делает текущую часть ленты недопустимой. Левому человеку нужно двигаться вперед, чтобы исправить это.
• Если левый человек двигается на 3 шага вперед, это значит, что следующие несколько шагов правого человека (right) не требуют движений от левого человека (left).

Заключение

Таким образом, даже если кажется, что вложенный цикл while может работать за O(n) на каждой итерации цикла for, на практике общее количество шагов, сделанных левым человеком (left), составляет не больше n шагов за весь процесс. Это называется амортизированным анализом: в худшем случае одна итерация может быть дорогой, но в среднем на каждую итерацию приходится всего лишь константное количество шагов.

Поэтому общая временная сложность остается O(n), потому что оба человека вместе делают максимум 2n шагов: n шагов правого человека и n шагов левого человека, которые распределяются по всему времени выполнения алгоритма.

Давайте рассмотрим несколько примеров:
https://leetcode.com/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/
https://leetcode.com/problems/minimum-size-subarray-sum/description/
https://leetcode.com/problems/subarray-product-less-than-k/description/
https://leetcode.com/problems/max-consecutive-ones-iii/description/

Фиксированный размер окна

В примерах, которые мы рассматривали выше, размер нашего окна был динамическим. Мы пытались расширить его вправо насколько это возможно, при этом удерживая окно в пределах некоторых ограничений, и удаляли элементы слева, когда эти ограничения нарушались. Иногда задача будет задавать фиксированную длину k.

Эти задачи просты, потому что разница между любыми двумя соседними окнами составляет всего два элемента (мы добавляем один элемент справа и удаляем один элемент слева, чтобы поддерживать длину).

Начните с построения первого окна (с индекса 0 до k - 1). Как только у нас есть окно размером k, если мы добавляем элемент в индексе i, нам нужно удалить элемент в индексе i - k. Например, если k = 2, и у нас есть элементы с индексами [0, 1]. Теперь мы добавляем 2: [0, 1, 2]. Чтобы сохранить размер окна k = 2, нам нужно удалить элемент с индексом 2 - k = 0: [1, 2].

Вот псевдокод для этого сценария:

function fn(arr, k):
    curr = some data to track the window

    // build the first window
    for (int i = 0; i < k; i++)
        Do something with curr or other variables to build first window

    ans = answer variable, probably equal to curr here depending on the problem
    for (int i = k; i < arr.length; i++)
        Add arr[i] to window
        Remove arr[i - k] from window
        Update ans

    return ans

Пример: https://leetcode.com/problems/maximum-average-subarray-i/description/