Разница между максимальным и минимальным средним значением всех смежных подмассивов длины K

Учитывая массив arr[] размера N и целое число K, задача состоит в том, чтобы напечатать разницу между максимальным и минимальным средним значением смежных подмассивов длины K .

Примеры:

Input: arr[ ] = {3, 8, 9, 15}, K = 2
Output: 6.5
Explanation:
All subarrays of length 2 are {3, 8}, {8, 9}, {9, 15} and their averages are (3+8)/2 = 5.5, (8+9)/2 = 8.5, and (9+15)/2 = 12.0 respectively. 
Therefore, the difference between the maximum(=12.0) and minimum(=5.5) is 12.0 -5.5 = 6.5.

Input: arr[] = {17, 6.2, 19, 3.4}, K = 3
Output: 4.533

Наивный подход: самый простой подход состоит в том, чтобы найти среднее значение каждого непрерывного подмассива размера K , а затем найти максимальное и минимальное значения и вывести их разницу.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*K)
Вспомогательное пространство: O(1)

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

• Найдите сумму подмассивов в диапазоне [0, K-1] и сохраните ее в переменной, скажем, sum .
• Инициализируйте две переменные, скажем, max и min , чтобы хранить максимальную и минимальную сумму любого подмассива размера K.
• Переберите диапазон [K, N-K+1] , используя переменную i , и выполните следующие шаги:
  • Удалите элемент arr[iK] и добавьте элемент arr[i] в окна размера K. Т.е. Обновите сумму до sum+arr[i]-arr[iK].
  • Обновите min как минимум min и sum и обновите max как максимум max и sum .
• Наконец, после выполнения вышеуказанных шагов выведите ответ в виде (max-min)/K.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)