Максимизируйте разницу целых чисел в подмассиве размера K

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

Input: arr = [2, 3, -1, -5, 4, 0], K = 3
Output: 9
Explanation: Subarray [-1, -5, 4] contains the maximum difference between -5 and -4 as 9

Input: arr = [-2, -4, 0, 1, 5, -6, 9], K =4
Output: 15
Explanation: Subarray [1, 5, -6, 9] contains the maximum difference between -6 and 9 as 15

Подход: Данная проблема может быть решена с использованием метода двух указателей и подхода скользящего окна со структурой данных TreeMap. Для решения проблемы можно выполнить следующие шаги:

• Перебрать массив arr до K – 1 и вставить элементы в TreeMap,
  • Если целое число уже присутствует в TreeMap, то увеличьте его частоту на 1
• Итерировать массив arr от K до конца массива, используя указатель вправо и на каждой итерации:
  • Вставьте элемент в TreeMap, если он не существует, или увеличьте его частоту на 1
  • Удалите крайний левый элемент скользящего окна, если его частота равна единице, или уменьшите его частоту на 1.
  • Вычислите разницу между максимальным и минимальным элементами, извлекая первый и последний элемент из treeMap, а также обновите результат res
• Вернуть результирующий результат

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