Замените каждый элемент массива максимум K следующими и K предыдущими элементами

Учитывая массив arr , задача состоит в том, чтобы заменить каждый элемент массива максимальным числом K следующих и K предыдущих элементов.

Пример:

Input: arr[] = {12, 5, 3, 9, 21, 36, 17}, K=2
Output: 5 12 21 36 36 21 36

Input: arr[] = { 13, 21, 19}, K=1
Output: 21, 19, 21 

Наивный подход: выполните следующие шаги, чтобы решить эту проблему:

1. Пройдите массив от i=0 до i<N и для каждого элемента:
   • Запустите еще один цикл от j=iK до j<=i+K и измените arr[i] на максимум K следующих и K предыдущих элементов.
2. Распечатайте массив после завершения вышеуказанного цикла.

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

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

Эффективный подход: для решения этой проблемы можно использовать дерево сегментов. Итак, постройте дерево сегментов максимального диапазона, где:

• Листовые узлы — это элементы входного массива.
• Каждый внутренний узел представляет максимум всех своих дочерних элементов.

Теперь, после построения дерева сегментов, найдите максимум от (iK) до (i-1) , скажем, слева , и максимум от (i+1) до (i+K) , скажем, справа, используя запрос к этому дереву сегментов. Замените arr[i] максимальным значением left и right .

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

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