Следующий больший элемент | Набор 2 (с использованием верхней границы)
Дан массив arr[ ] из n целых чисел. Задача состоит в том, чтобы найти первый больший элемент для каждого элемента массива в массиве, используя функцию upper_bound(). Если для любого элемента массива нет большего элемента, верните -1 .
Примеры :
Input: n = 7, arr[ ] = {4, 7, 3, 1, 3, 2, 5}
Output: 7 -1 4 4 4 4 7
Explanation : First greater element for first, third, fourth, fifth, sixth and last element are 7, 4, 4, 4, 4, and 7 . Second element of arr[ ] do not have it’s first greater element of itself.Input : n = 4, arr[ ] = {2, 8, 8, 1}
Output : 8 -1 -1 2
Explanation : First greater element for first and last element are 8 and 2 . Second and third element of arr[ ] do not have it’s first greater element of itself .
Наивный подход . Наивный подход и стековый подход обсуждаются в наборе 1 этой статьи. Здесь мы обсудили метод решения этой проблемы с помощью upper_bound().
Подход: поскольку upper_bound() нельзя применять к несортированному массиву. Идея состоит в том, чтобы попытаться изменить массив, чтобы он стал отсортированным. Итак, создайте массив, назовем его copy[] , элементы которого будут отсортированы. Сначала инициализируйте copy[ ] значением 0 и обновите каждый элемент copy[ ] следующим образом: copy[i] = max(copy[i-1], arr[i]) . Теперь upper_bound() можно применить к копии [ ] и найти первый больший элемент для каждого arr[i] . Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте массив copy[n] со значениями 0 .
- Переберите диапазон [1, n), используя переменную i , и выполните следующие шаги:
- Установите значение copy[i] как максимальное значение copy[i-1] или arr[i].
- Переберите диапазон [0, n), используя переменную i , и выполните следующие шаги:
- Инициализируйте переменную high как верхнюю границу arr[i] в массиве copy[] .
- Если high равно n , то выведите -1, иначе выведите arr[high].
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O (n * log (n))
Вспомогательное пространство: O(n)