Найти индекс элемента, который меньше i

Question

У меня есть массив. Например [7, 2, 1, 4, 5, 1, 3, 3]. С помощью такого кода я нахожу ближайший элемент к h[i], который меньше h[i]

inf = int(2e9) + 1
n = int(input())
h = [-inf] + [int(x) for x in input().split()] + [-inf]
ans = [0] * (n+2)
st = [0]
for i in range(1, n + 2):
    while h[st[-1]] > h[i]:
        ans[st.pop()] = i
    st.append(i)
for i in range(1, n + 1):
    if ans[i] == n+1:
        print(-1,end = " ")
    else:
        print(ans[i]-1, end = " ")
print()

Мне нужно сделать тоже самое, но чтобы цикл работал в левую сторону. Например, для элементов 7, 2 и 1 программа не найдёт элементов, которые стоят левее i и при этом меньше h[i]. А вот для элемента 4 ответ должен быть 2(индекс элемента 1).

Answer 1

Используем стек, в котором будут храниться индексы кандидатов.

На каждом шаге сравним вершину стека с текущим элементом и будем удалять вершину, пока она не станет меньше (у удалённых элементов уже нет шансов стать меньшими предшественниками). Теперь на вершине индекс нужного элемента.

Если стек становится пустым - у текущего элемента нет меньшего левого.

Положить индекс текущего на стек.

a = [7, 2, 1, 4, 5, 1, 3, 3]
st = []
leftless = []
for i in range(len(a)):
    while len(st) > 0 and a[st[-1]] >= a[i]:
        st.pop()
    if len(st) > 0:
        leftless.append(st[-1])
    else:
        leftless.append(-1)
    st.append(i)
print(leftless)

>>[-1, -1, -1, 2, 3, -1, 5, 5]

БЛОГ НА HUSL

Найти индекс элемента, который меньше i

Ответы (1 шт):