Как найти предыдущий наименьший элемент данного индекса в массиве?

Question

Например, у меня есть

input array 
[1,3,5,6,4,8,4,3,2,1]

output should be [-1 , 1, 3, 5, 3 , 6, 3, 1, 1, -1]

Объяснение: давайте сохраним первый элемент как -1, так как нет меньшегоодин до этого.

In index '1' the previous smaller element to 3 needs to be stored. i.e 1.

In index '2' the previous smaller element to 5 needs to be stored. i.e 3. & so on...

Я знаю, что могу решить эту проблему в сложности O (n2).Но я хотел бы решить эту проблему в O (N) сложности.Я пытался, но я не могу это сделать.

Пожалуйста, помогите мне решить эту проблему.Заранее спасибо.

Answer 1

O (n), вероятно, невозможно, но я могу дать вам подход O (n log n).Создайте сбалансированный BST (структура набора / словаря в большинстве языков программирования).Теперь вы можете легко найти наибольшее число, меньшее x, пройдя по дереву.

Структура набора / словаря часто имеет встроенную функцию, называемую верхней границей, которая находит ваш наименьший элемент больше x (или наибольший меньше, еслиВы решаете изменить порядок сортировки).Вы также можете использовать это.

Все, что вам нужно сделать, это:

Для каждого значения v в массиве:

• найти наибольшее число меньшечем v в BST,

• вставить v в BST

Answer 2

Я думаю, вы хотите решить это за O (n) время.Вы можете найти свой ответ здесь: https://www.geeksforgeeks.org/find-the-nearest-smaller-numbers-on-left-side-in-an-array/