Для каждого индекса массива найдите максимальное значение среди всех M операций.

Опубликовано: 19 Сентября, 2022

Учитывая массив arr[] размера N , изначально заполненный 0, и другой массив Positions[] размера M , задача состоит в том, чтобы вернуть максимальное значение для каждого индекса после выполнения следующих M операций:

  • Сделать значение в индексе Positions[i] равным 0
  • Все числа справа от Positions[i] будут на единицу больше, чем их ближайшие левые соседи.
  • Все числа слева от Positions[i] будут на единицу больше, чем их ближайшие правые соседи.

Примеры:

Input: N = 6, M = 2, Positions = {2, 3}
Output: {3, 2, 1, 1, 2, 3}
Explanation: Initial array: {0, 0, 0, 0, 0, 0} 
After first operation: {2, 1, 0, 1, 2, 3} 
where each element to the right of 2nd index and each element to its left follow the given condition
After second operation:  {3, 2, 1, 0, 1, 2}
Thus, maximum value of each index among all the operations: {3, 2, 1, 1, 2, 3}

Input: N = 4, M = 3, Positions = {3, 2, 1}
Output: {3, 2, 1, 2}
Explanation: Initial array: {0, 0, 0, 0} 
After first operation:  {3, 2, 1, 0}
After second operation:  {2, 1, 0, 1}
After third operation: {1, 0, 1, 2}
Thus, Maximum: {3, 2, 1, 2}

Подход: Задача может быть решена на основе следующего наблюдения:

The value set at the indices for each operation denotes the distance from the index set to 0. 
Therefore, the positions closest to the ends of the array which are set to 0 will set the values of other indices to be the maximum when given operation is performed. 

Основываясь на приведенном выше наблюдении, решение состоит в том, чтобы найти индексы, ближайшие к концам массива (скажем, x и y ), которые установлены на 0 в любой из операций. Максимальное значение для каждого индекса будет максимальным расстоянием от любого из x и y .

Следуйте инструкциям, чтобы решить проблему:

  • Создайте массив с нулевыми значениями (скажем, arr[] ).
  • Найдите максимум и минимум в массиве Positions[] (скажем, x и y ).
  • Пройдите массив от i = 0 до N-1 :
    • Выведите максимум абсолютной разницы между текущим индексом и x или y

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

Временная сложность: O(N) + O(M), где N — размер массива, а M — размер массива позиций.
Вспомогательное пространство: O(M)

РЕКОМЕНДУЕМЫЕ СТАТЬИ