Создайте массив, заменив любой элемент его ближайшим меньшим соседом

Учитывая целочисленный массив arr[] размера N , задача состоит в том, чтобы сгенерировать новый массив, заменив i ^-й элемент его ближайшим правым меньшим соседом, т. е. на (i+t) ^-й элемент, если он меньше.

Примеры:

Input: N = 5, Arr[] = {4, 2, 1, 5, 3}
Output: 2 1 -1 3 -1
Explanation: Array elements are 4, 2, 1, 5, 3.
Next to 4 is 2 which is smaller, so we print 2. Next of 2 is 1 which is smaller, so we print 1. Next of 1 is 5 which is greater, so we print -1. Next of 5 is 3 which is smaller, so we print 3.  Note that for last element, output is always  going to be -1 because there is no element on right.

Input: N = 6, Arr[] = {5, 6, 2, 3, 1, 7}
Output: -1 2 -1 1 -1 -1

Подход: Чтобы решить проблему, следуйте следующей идее:

The idea is to traverse the array and check if the next element is smaller or not. If next element is smaller then replace current element with next smaller element otherwise replace current element with -1.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Перебрать массив от i = 0 до i < size of array – 1
  • Проверить, больше ли текущий элемент, чем следующий элемент (т. е. arr[i] > arr[i + 1])
    • Если верно, замените arr[i] = arr[i + 1]
    • В противном случае замените arr[i] = -1

Ниже приведена реализация описанного выше подхода.

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