Когда дело доходит до решения проблем с алгоритмами, есть несколько чрезвычайно полезных шаблонов (шаблон алгоритма или парадигма алгоритма — это метод, стратегия или техника решения проблемы), которые сделают нашу жизнь намного проще. «Скользящее окно» — распространенный шаблон решения задач в информатике. Чаще всего он используется для массивов и строк. Основной принцип заключается в том, чтобы создать «окно», а затем проверить, удовлетворяют ли данные в окне условию вашей задачи, а также преобразовать два вложенных цикла в один цикл. В конце этой статьи вы найдете полезные ресурсы, которые помогут вам с этим шаблоном.
ключевые слова: найдите минимальное, максимальное, самое короткое или самое длинное.
Получить репозиторий этих примеров: https://github.com/LuisSalas94/Sliding-Window-Pattern-Article
Пример 01:
Постановка задачи
Для заданного массива найдите среднее значение всех подмассивов из «k» смежных элементов в нем.
Массив: [1, 3, 2, 6, -1, 4, 1, 8, 2], k = 5
Здесь нас просят найти среднее значение всех подмассивов из «5» смежных элементов в данном массиве. Давайте решим это:
- Для первых 5 чисел (подмассив из индекса 0–4) среднее значение равно (1 + 3 + 2 + 6–1) / 5 => 2,2
- Среднее значение следующих 5 чисел (подмассив из индекса 1–5): (3 + 2 + 6–1 + 4) / 5 => 2,8
- Для следующих 5 подмассивов чисел (подмассив из индекса 2–6) среднее: (2 + 6–1 + 4 + 1) / 5 => 2,4
Вот окончательный вывод, содержащий среднее значение всех подмассивов размера 5:
Выход: [2.2, 2.8, 2.4, 3.6, 2.8]
Алгоритм грубой силы рассчитает сумму каждого 5-элементного подмассива данного массива и разделит сумму на «5», чтобы найти среднее значение.
Есть ли лучшее решение? Нашли ли вы какую-либо неэффективность в приведенном выше подходе? На самом деле есть лучшее решение: эффективным способом решения этой проблемы было бы визуализировать каждый подмассив как скользящее окно из «5» элементов. Это означает, что мы сдвинем окно на один элемент при переходе к следующему подмассиву. Чтобы повторно использовать сумму из предыдущего подмассива, мы вычтем элемент, выходящий за пределы окна, и добавим элемент, который сейчас включается в скользящее окно.
Пример 02:
Постановка задачи
Учитывая массив положительных чисел и положительное число «k», найдите максимальную сумму любого непрерывного подмассива размера «k».
Массив: [2, 1, 5, 1, 3, 2], k = 3
Для этого каждый подмассив следует рассматривать как скользящее окно размера «k». Чтобы вычислить сумму следующего подмассива, нам нужно сдвинуть окно вперед на один элемент. Итак, чтобы сдвинуть окно вперед и вычислить сумму новой позиции скользящего окна, необходимы две вещи:
- Вычесть элемент, выходящий из скользящего окна, т. е. вычесть первый элемент окна.
- Добавьте новый элемент, включаемый в скользящее окно, т. е. элемент, следующий сразу за концом окна.
Пример 03:
Постановка задачи
Учитывая массив положительных чисел и положительное число «S», найдите длину наименьшего непрерывного подмассива, сумма которого больше или равна «S». Возвращает 0, если такой подмассив не найден.
Массив: [2, 1, 5, 2, 3, 2], S = 7
Вывод: 2
Объяснение: Наименьший подмассив с суммой больше или равной 7 — это [5, 2].
Мы можем использовать аналогичную стратегию, как обсуждалось в подмассиве максимальной суммы размера k. Однако есть одно отличие: в этой задаче размер скользящего окна не фиксирован. Вот как мы решим эту проблему.
Удивительная особенность задач со скользящим окном заключается в том, что в большинстве случаев их можно решить за O(N) времени и O(1) пространственной сложности.