Метод "ковзного вікна" (Sliding Window) є одним із найефективніших підходів до вирішення задач, що включають суміжні підмасиви (subarrays) або підстроки (substrings). Цей метод значно знижує часову складність у порівнянні з методами грубої сили (brute-force), що робить його незамінним інструментом у арсеналі кожного програміста.

У цій статті ми розглянемо задачі з "ковзним вікном", розділивши їх на два типи: фіксоване вікно (Fixed Size Window) та змінне вікно (Variable Size Window).

A. Фіксоване вікно

Фіксоване ковзне вікно передбачає обробку підмасивів або підстрок певної довжини у вхідній послідовності. Це особливо корисно для задач, де потрібно проаналізувати кожен суміжний сегмент розміру k.

1. Максимальна/мінімальна сума підмасиву розміру k

Задача 1: Дано масив, знайти максимальну (або мінімальну) суму підмасиву розміру k.

Підхід до вирішення:

• Використовуйте метод ковзного вікна для підтримки суми поточного підмасиву розміру k.
• Зрушуйте вікно по масиву, ефективно оновлюючи суму шляхом видалення вихідного елемента та додавання нового.

Метод грубої сили (Brute Force) проти методу "ковзного вікна" (Sliding Window)

# Метод грубої сили  
def max_subarray_sum_brute_force(arr, k):  
 if len(arr) < k:  
 return None # Недостатньо елементів для підмасиву розміру k  

 max_sum = float('-inf') # Ініціалізуємо max_sum як мінус нескінченність  

 for i in range(len(arr) - k + 1): # Цикл по всіх можливих підмасивах розміру k  
 current_sum = sum(arr[i:i + k]) # Обчислюємо суму підмасиву від i до i+k-1  
 max_sum = max(max_sum, current_sum) # Оновлюємо max_sum, якщо current_sum більша  

 return max_sum  
# Приклад використання  
arr = [2, 1, 5, 1, 3, 2]  
k = 3  
print(max_subarray_sum_brute_force(arr, k)) # Вивід: 9

# Метод "ковзного вікна"  
def maximum_subarray_sum(arry, k):  
 if len(arry) < k:  
 return None # Недостатньо елементів для підмасиву розміру k  
 i, j = 0, 0  
 sum_1 = 0  
 max_1 = float('-inf') # Ініціалізуємо max_sum як мінус нескінченність  
 while j < len(arry):  
 sum_1 += arry[j] # Додаємо поточний елемент до вікна  
 if j - i + 1 == k: # Коли розмір вікна досягає k  
 max_1 = max(max_1, sum_1) # Оновлюємо max_sum  
 sum_1 -= arry[i] # Видаляємо перший елемент із вікна  
 i += 1 # Зсуваємо вікно  
 j += 1 # Розширюємо вікно  
 return max_1  
# Приклад використання  
arr = [2, 1, 5, 1, 3, 2]  
k = 3  
print(maximum_subarray_sum(arr, k)) # Вивід: 9 (підмасив [5, 1, 3])

Аналіз складності: метод грубої сили проти "ковзного вікна"

Метод грубої сили

Аналіз часової складності:

• Зовнішній цикл виконується O(N) разів.
• Кожна ітерація обчислює суму k елементів → O(k).
• Загальна часова складність: O(N×k). Це неефективно для великих N.

Складність за пам'яттю:

• O(1) (постійна пам'ять), оскільки використовуються лише кілька змінних.

Метод "ковзного вікна"

Аналіз часової складності:

• Спочатку обчислюється сума перших k елементів → O(k).
• Потім ітеруємо через решту масиву, оновлюючи суму за постійний час → O(N−k).
• Загальна часова складність: O(N). Це значно ефективніше, ніж метод грубої сили.

Складність за пам'яттю:

• O(1) (постійна пам'ять), оскільки використовуються лише кілька додаткових змінних.

| Підхід | Часова складність | Складність за пам’яттю | Ефективність |
|----------------------|-----------------------|----------------------------|------------------------------|
| Метод грубої сили | O(N×k) | O(1) | Повільний для великих N |
| Метод "ковзного вікна" | O(N) | O(1) | Швидкий та ефективний |

2. Перший від’ємний елемент у кожному вікні розміру k

Задача 2: Дано масив цілих чисел, для кожного підмасиву розміру k знайти перший від’ємний елемент.
Якщо такого числа немає, поверніть 0.

Підхід до вирішення:

• Використовуйте чергу (queue) для зберігання індексів від’ємних чисел.
• Під час зсуву вікна оновлюйте чергу та ефективно отримуйте перший від’ємний елемент.

Метод грубої сили (Brute Force) проти методу "ковзного вікна" (Sliding Window)

#Метод грубої сили  
def first_negative_value_brute_force(arr, k):  
 n = len(arr)  
 first_neg = []  

 for i in range(n - k + 1): # Ітерація по всіх можливих підмасивах розміру k  
 found = False  
 for j in range(i, i + k): # Перевірка елементів у поточному вікні  
 if arr[j] < 0:  
 first_neg.append(arr[j]) # Додати перше від’ємне число  
 found = True  
 break # Зупинити пошук після знаходження першого від’ємного  
 if not found:  
 first_neg.append(0) # Якщо від’ємного числа не знайдено, додати 0  

 return first_neg  

# Приклад використання  
arr = [2, -1, 3, -4, 5, -6, 7, -8, 9]  
k = 3  
print(first_negative_value_brute_force(arr, k))   
# Вивід: [-1, -1, -4, -4, -6, -6, -8]

#Метод "ковзного вікна"  
def first_nagative_value(arry,k):  
 n=len(arry)  
 current_neg=[]  
 first_neg=[]  
 i,j=0,0  
 while j

## Максимум для всіх підмасивів розміру k

**Задача 4:** Дано масив, знайти максимальне значення у кожному підмасиві розміру `k`.

**Підхід до вирішення:**

- Використовуйте дек (deque, двостороння черга) для збереження індексів елементів у порядку спадання.
- Переконайтеся, що максимальний елемент у поточному вікні завжди знаходиться на початку дека.

**Метод грубої сили (Brute Force) проти методу "ковзного вікна" (Sliding Window)**

Метод грубої сили

def maxinsubarraysbruteforce(arr, k):
n = len(arr)
result = []

for i in range(n - k + 1): # Ітерація по всіх можливих підмасивах розміру k
maxvalue = arr[i] # Припустимо, що перший елемент є максимальним
for j in range(i, i + k): # Перевіряємо всі елементи в межах вікна
if arr[j] > maxvalue:
maxvalue = arr[j] # Оновлюємо maxvalue, якщо знайдено більший елемент
result.append(max_value) # Додаємо максимум для поточного вікна

return result

Приклад використання

arr = [2, 6, 7, 1, 9, 3, 5, 8]
k = int(input("Введіть розмір підмасиву: "))

result = maxinsubarraysbruteforce(arr, k)
print("Максимум у кожному підмасиві:", result)
```

# Метод "ковзного вікна"  
def max_in_subarrays(arr, k):  
 n = len(arr)  
 q = [] # Список для збереження індексів  
 result = []  

 for i in range(n):  
 # Видаляємо елементи, які не входять у поточне вікно  
 while q and q[0] < i - k + 1:  
 q.pop(0)  

 # Видаляємо всі елементи, менші за поточний елемент  
 while q and arr[q[-1]] < arr[i]:  
 q.pop()  

 # Додаємо індекс поточного елемента до списку  
 q.append(i)  

 # Додаємо максимум вікна до результату  
 if i >= k - 1:  
 result.append(arr[q[0]])  

 return result  

# Приклад використання  
arr = [2, 6, 7, 1, 9, 3, 5, 8]  
k = int(input("Введіть розмір підмасиву: "))  

result = max_in_subarrays(arr, k)  
print("Максимум у кожному підмасиві:", result)

Порівняння часової та просторової складності

| Підхід | Часова складність | Складність за пам’яттю | Ефективність |
|------------------------|-----------------------|----------------------------|------------------------------|
| Метод грубої сили | O(N×k) | O(1) | Повільний для великих N |
| Оптимізований метод "ковзного вікна" | O(N) | O(k) | Швидкий та ефективний |

Максимум із мінімумів кожного підмасиву розміру k

Задача 5: Дано масив, знайти максимальне значення серед мінімальних значень усіх підмасивів розміру k.

Підхід до вирішення:

• Використовуйте дек (deque) для відстеження мінімальних елементів у поточному вікні.
• Зсувайте вікно, ефективно оновлюючи дек.

Метод грубої сили (Brute Force) проти методу "ковзного вікна" (Sliding Window)

# Метод грубої сили  
def max_of_minimums_brute_force(arr, k):  
 n = len(arr)  
 if k > n:  
 return None # Крайній випадок: розмір підмасиву більший за розмір масиву  

 max_min = float('-inf') # Для збереження максимального серед мінімальних значень  

 for i in range(n - k + 1): # Ітерація по всіх можливих підмасивах розміру k  
 current_min = float('inf') # Ініціалізація мінімуму для поточного вікна  
 for j in range(i, i + k): # Ітерація по підмасиву  
 current_min = min(current_min, arr[j]) # Оновлення мінімуму в межах вікна  
 max_min = max(max_min, current_min) # Оновлення максимального серед мінімумів  

 return max_min  

# Приклад використання  
arr = [10, 20, 10, 50, 10, 70, 30]  
k = 3  
result = max_of_minimums_brute_force(arr, k)  
print("Максимум серед мінімумів:", result)

# Метод "ковзного вікна"  
def max_of_minimums_sliding_window_list(arr, k):  
 n = len(arr)  
 if k > n:  
 return None # Крайній випадок: розмір підмасиву більший за розмір масиву  

 window = [] # Список для збереження індексів мінімальних елементів  
 max_min = float('-inf') # Для збереження максимального серед мінімальних значень  

 for i in range(n):  
 # Видалення елементів, які виходять за межі поточного вікна  
 if window and window[0] < i - k + 1:  
 window.pop(0)  

 # Видалення елементів з кінця, які не є корисними (більші елементи)  
 while window and arr[window[-1]] > arr[i]:  
 window.pop()  

 # Додавання індексу поточного елемента до списку  
 window.append(i)  

 # Коли опрацьовано принаймні `k` елементів, враховуємо мінімум  
 if i >= k - 1:  
 max_min = max(max_min, arr[window[0]]) # arr[window[0]] — це мінімум у вікні  

 return max_min  

# Приклад використання  
arr = [10, 20, 10, 50, 10, 70, 30]  
k = 3  
result = max_of_minimums_sliding_window_list(arr, k)  
print("Максимум серед мінімумів:", result)

Часова та просторова складність

| Підхід | Часова складність | Складність за пам’яттю | Ефективність |
|------------------------|-----------------------|----------------------------|------------------------------|
| Метод грубої сили | O(N×k) | O(1) | Повільний для великих N |
| Метод "ковзного вікна" | O(N) | O(k) | Швидкий та ефективний |

Змінне ковзне вікно

Змінне ковзне вікно корисне, коли розмір вікна не є заздалегідь визначеним, і ми маємо динамічно розширювати або звужувати вікно залежно від умов.

Найбільший/найменший підмасив із сумою k

Задача 6: Дано масив і суму k, знайти найбільший (або найменший) підмасив, чия сума дорівнює k.

Підхід до вирішення:

• Використовуйте два вказівники (left і right) для динамічного розширення та скорочення вікна.
• Ефективно оновлюйте суму в процесі зміни вікна.

Метод грубої сили (Brute Force) проти методу "ковзного вікна" (Sliding Window)

# Метод грубої сили  
def largest_subarray_with_sum_k_brute_force(arr, k):  
 n = len(arr)  
 max_length = 0  

 # Перевіряємо всі можливі підмасиви  
 for i in range(n):  
 current_sum = 0  
 for j in range(i, n):  
 current_sum += arr[j] # Сума підмасиву від i до j  
 if current_sum == k:  
 max_length = max(max_length, j - i + 1)  

 return max_length  

# Приклад використання  
arr = [2, 6, 7, 1, 9, 3, 5, 8]  
k = int(input("Введіть суму k: "))  

result = largest_subarray_with_sum_k_brute_force(arr, k)  
print("Довжина найбільшого підмасиву із сумою k:", result)

# Метод "ковзного вікна"  
# Функція для знаходження найбільшого або найменшого підмасиву із сумою k  
def largest_subarray_with_sum_k(arr, k):  
 sum_map = {}  
 max_length = 0  
 current_sum = 0  

 for i in range(len(arr)):  
 current_sum += arr[i]  

 # Якщо поточна сума дорівнює k  
 if current_sum == k:  
 max_length = i + 1  

 # Якщо current_sum - k існує в мапі, оновлюємо max_length  
 if current_sum - k in sum_map:  
 max_length = max(max_length, i - sum_map[current_sum - k])  

 # Зберігаємо перше входження поточної суми  
 if current_sum not in sum_map:  
 sum_map[current_sum] = i  

 return max_length  

# Приклад використання  
arr = [2, 6, 7, 1, 9, 3, 5, 8]  
k = int(input("Введіть суму k: "))  

result = largest_subarray_with_sum_k(arr, k)  
print("Довжина найбільшого підмасиву із сумою k:", result)

Часова та просторова складність

| Підхід | Часова складність | Складність за пам’яттю | Ефективність |
|------------------------|-----------------------|----------------------------|------------------------------|
| Метод грубої сили | O(N²) | O(1) | Дуже повільний для великих N |
| Оптимізований метод | O(N) | O(N) | Швидкий та ефективний |

Найбільший підрядок із k унікальними символами

Задача 7: Дано рядок, знайти довжину найбільшого підрядка, який містить рівно k унікальних символів.

Підхід до вирішення:

• Використовуйте хешмапу (hashmap) для відстеження частот символів.
• Розширюйте вікно, підтримуючи рівно k унікальних символів.

Аналіз складності: метод грубої сили (Brute Force) проти методу "ковзного вікна" (Sliding Window)

# Метод грубої сили  
def longest_substring_with_k_distinct_brute_force(s, k):  
 n = len(s)  
 max_length = 0  

 # Перевіряємо всі підрядки  
 for i in range(n):  
 distinct_chars = set()  
 for j in range(i, n):  
 distinct_chars.add(s[j])  

 # Перевіряємо, чи має підрядок не більше ніж k унікальних символів  
 if len(distinct_chars) > k:  
 break # Зупиняємо розширення цього підрядка  

 max_length = max(max_length, j - i + 1)  

 return max_length  

# Приклад використання  
s = input("Введіть рядок: ")  
k = int(input("Введіть кількість унікальних символів k: "))  

result = longest_substring_with_k_distinct_brute_force(s, k)  
print("Найдовший підрядок із не більше ніж k унікальними символами:", result)

# Метод "ковзного вікна"  

def longest_substring_with_k_distinct(s, k):  
 n = len(s)  
 char_map = {}  
 max_length = 0  
 left = 0  

 for right in range(n):  
 char_map[s[right]] = char_map.get(s[right], 0) + 1  

 while len(char_map) > k:  
 char_map[s[left]] -= 1  
 if char_map[s[left]] == 0:  
 del char_map[s[left]]  
 left += 1  

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

 return max_length  

# Приклад використання  
s = input("Введіть рядок: ")  
k = int(input("Введіть кількість унікальних символів k: "))  

result = longest_substring_with_k_distinct(s, k)  
print(result)

Часова та просторова складність

| Підхід | Часова складність | Складність за пам’яттю | Ефективність |
|------------------------|-----------------------|----------------------------|------------------------------|
| Метод грубої сили | O(N²) | O(K) | Повільний для великих N |
| Метод "ковзного вікна" | O(N) | O(K) | Значно швидший |

Довжина найбільшого підрядка без повторюваних символів

Задача 8: Дано рядок, знайти довжину найбільшого підрядка без повторюваних символів.

Підхід до вирішення:

• Використовуйте множину (set) для відстеження унікальних символів.
• Розширюйте вікно, забезпечуючи відсутність дублікатів.

Аналіз складності: метод грубої сили (Brute Force) проти методу "ковзного вікна" (Sliding Window)

# Метод грубої сили   
def longest_substring_without_repeating_brute_force(s):  
 n = len(s)  
 max_length = 0  

 # Перевіряємо всі підрядки  
 for i in range(n):  
 seen_chars = set()  
 for j in range(i, n):  
 if s[j] in seen_chars: # Якщо символ повторюється, зупиняємо  
 break  
 seen_chars.add(s[j])  
 max_length = max(max_length, j - i + 1)  

 return max_length  

# Приклад використання  
s = input("Введіть рядок: ")  
result = longest_substring_without_repeating_brute_force(s)  
print("Найдовший підрядок без повторюваних символів:", result)

# Метод "ковзного вікна"  
def longest_substring_without_repeating(s):  
 n = len(s)  
 char_map = {}  
 max_length = 0  
 left = 0  

 for right in range(n):  
 if s[right] in char_map:  
 left = max(left, char_map[s[right]] + 1)  

 char_map[s[right]] = right  
 max_length = max(max_length, right - left + 1)  

 return max_length  

# Приклад використання  
s = input("Введіть рядок: ")  
result = longest_substring_without_repeating(s)  
print(result)

| Підхід | Часова складність | Складність за пам’яттю | Ефективність |
|------------------------|-----------------------|----------------------------|------------------------------|
| Метод грубої сили | O(N²) | O(N) | Повільний для великих N |
| Метод "ковзного вікна" | O(N) | O(N) | Значно швидший |

Вибір іграшок (або підмасив із певними умовами)

Задача 9: Дано масив, знайти найбільший підмасив, який можна вибрати, щоб він задовольняв певні умови (наприклад, вибір іграшок у межах обмеження ваги).

Підхід до вирішення:

• Подібно до задачі з k унікальними символами, використовуйте карту частот (frequency map).
• Розширюйте та скорочуйте вікно, щоб задовольнити задану умову.

Аналіз складності: метод грубої сили (Brute Force) проти методу "ковзного вікна" (Sliding Window)

# Метод грубої сили  
def longest_substring_without_repeating_brute_force(s):  
 n = len(s)  
 max_length = 0  

 # Перевіряємо всі підрядки  
 for i in range(n):  
 seen_chars = set()  
 for j in range(i, n):  
 if s[j] in seen_chars: # Якщо символ повторюється, зупиняємо  
 break  
 seen_chars.add(s[j])  
 max_length = max(max_length, j - i + 1)  

 return max_length  

# Приклад використання  
s = input("Введіть рядок: ")  
result = longest_substring_without_repeating_brute_force(s)  
print("Найдовший підрядок без повторюваних символів:", result)

# Метод "ковзного вікна"  
def longest_substring_without_repeating(s):  
 n = len(s)  
 char_map = {}  
 max_length = 0  
 left = 0  

 for right in range(n):  
 if s[right] in char_map:  
 left = max(left, char_map[s[right]] + 1)  

 char_map[s[right]] = right  
 max_length = max(max_length, right - left + 1)  

 return max_length  

# Приклад використання  
s = input("Введіть рядок: ")  
result = longest_substring_without_repeating(s)  
print(result)

Часова та просторова складність

| Підхід | Часова складність | Складність за пам’яттю | Ефективність |
|------------------------|-----------------------|----------------------------|------------------------------|
| Метод грубої сили | O(N²) | O(N) | Повільний для великих N |
| Метод "ковзного вікна" | O(N) | O(N) | Значно швидший |

Мінімальний підрядок

Задача 10: Дано два рядки s і t. Знайти мінімальний підрядок у s, який містить усі символи з t.

Підхід до вирішення:

• Використовуйте карту частот (frequency map) для відстеження необхідних символів.
• Розширюйте вікно, доки всі символи не будуть включені, потім скорочуйте його, щоб знайти найменше можливе валідне вікно.

Аналіз складності: метод грубої сили (Brute Force) проти методу "ковзного вікна" (Sliding Window)

from collections import Counter  

def min_window_brute_force(s, t):  
 if not s or not t:  
 return ""  

 t_counter = Counter(t)  
 min_length = float("inf")  
 ans = ""  

 # Генеруємо всі можливі підрядки рядка s  
 for i in range(len(s)):  
 for j in range(i + 1, len(s) + 1):  
 # Отримуємо поточний підрядок  
 current_substring = s[i:j]  

 # Якщо поточний підрядок містить усі символи з t  
 if all(current_substring.count(char) >= t_counter[char] for char in t_counter):  
 # Оновлюємо відповідь, якщо знайдено менший валідний підрядок  
 if len(current_substring) < min_length:  
 min_length = len(current_substring)  
 ans = current_substring  

 return ans  

# Приклад використання  
s = input("Введіть рядок s: ")  
t = input("Введіть рядок t: ")  
result = min_window_brute_force(s, t)  
print(result)

from collections import Counter  

def min_window(s, t):  
 if not s or not t:  
 return ""  

 # Карта частот символів у t  
 t_counter = Counter(t)  
 current_counter = Counter()  

 required = len(t_counter)  
 formed = 0  

 left = 0  
 right = 0  
 min_length = float("inf")  
 ans = (0, 0)  

 # Розширюємо вікно правим вказівником  
 while right < len(s):  
 current_counter[s[right]] += 1  

 # Якщо поточне вікно містить усі символи з t  
 if s[right] in t_counter and current_counter[s[right]] == t_counter[s[right]]:  
 formed += 1  

 # Скорочуємо вікно зліва, щоб знайти найменше валідне вікно  
 while left <= right and formed == required:  
 if right - left + 1 < min_length:  
 min_length = right - left + 1  
 ans = (left, right)  

 # Скорочуємо вікно зліва  
 current_counter[s[left]] -= 1  
 if s[left] in t_counter and current_counter[s[left]] < t_counter[s[left]]:  
 formed -= 1  
 left += 1  

 right += 1  

 # Якщо знайдено валідне вікно, повертаємо підрядок, інакше повертаємо порожній рядок  
 return s[ans[0]:ans[1] + 1] if min_length != float("inf") else ""  

# Приклад використання  
s = input("Введіть рядок s: ")  
t = input("Введіть рядок t: ")  
result = min_window(s, t)  
print(result)

Часова та просторова складність

| Підхід | Часова складність | Складність за пам’яттю | Ефективність |
|------------------------|-----------------------|----------------------------|------------------------------|
| Метод грубої сили | O(N³) | O(N) | Дуже неефективний для великих рядків |
| Оптимізований метод | O(N) | O(N) | Значно ефективніший |

Перекладено з: Mastering the Sliding Window Technique: A Guide to Optimized Problem-Solving