Считать соседнее меньшее число в списке с O (n) RunTime?

Question

Меня попросили запрограммировать функцию, которая запускается в списке, и для каждого его индекса подсчитывает количество значений, которые были меньше, чем текущий и рядом с ним.например, в индексе 5 значение «75» больше, чем 60,70,60.

Ввод:

(100,80,60,70,60,75,85) 

Вывод системы:

(0,0,0,1,0,3,5)

Iбыло предложено сделать это RunTime из O (n) и с помощью класса стека.и я довольно невежественен.

Я предполагаю, что это как-то связано с рекурсивными

решениями на любом другом языке, которые будут очень полезны

Answer 1

В python это можно сделать с помощью List, который имеет методы pop и push (как используется в стеке). Код выглядит примерно так:

a = [100,80,60,70,60,75,85]
out = []
for i in a:
    out.append(len([i for j in a if i>j] ))
print out