Найдите все элементы массива, которые меньше, чем все элементы справа от них

Дан массив arr[] , содержащий N положительных целых чисел. Задача состоит в том, чтобы найти все элементы, которые меньше всех элементов справа от них.

Примеры:

Input: arr[] = {6, 14, 13, 21, 17, 19}
Output: [6, 13, 17, 19]
Explanation: All the elements in the output are following the condition.

Input: arr[] = {10, 3, 4, 8, 7}
Output: [3, 4, 7]

Наивный подход: этот подход использует два цикла. Для каждого элемента пройдите массив вправо и проверьте, существует ли какой-либо меньший элемент или нет. Если все элементы в правой части массива больше его, то выведите этот элемент.

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

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

• Итерировать массив с начала массива.
• Для каждого элемента в массиве извлеките все элементы, присутствующие в стеке, которые больше его, а затем поместите их в стек.
• Если ни один элемент не больше его, то текущий элемент является ответом.
• Наконец, стек остается с элементами, которые меньше, чем все элементы, находящиеся справа от них.

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

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

Подход, оптимизированный по пространству: идея состоит в том, чтобы пройти массив справа налево (обратный порядок) и сохранить вспомогательную переменную, которая хранит минимальный найденный элемент. Этот подход будет пренебрегать использованием стека. Выполните следующие шаги:

• Начните итерацию с конца массива.
• Если текущий элемент меньше минимального на данный момент, то элемент найден. Обновите значение, сохраняющее минимальное значение на данный момент. Выведите все такие значения в качестве ответа.

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

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