next_greater: ближайший справа строго больший элемент за один проход
Напишите функцию next_greater(nums: list[int]) -> list[int].
Вход. Список целых чисел nums (могут быть нули, отрицательные, дубликаты).
Выход. Новый список той же длины, что и nums. На позиции i стоит первый элемент справа от nums[i], который строго больше nums[i]. Если такого нет — -1.
Поведение на краевых входах.
- Пустой список — вернуть пустой список.
- Один элемент — вернуть
[-1]. - Равный элемент справа большим не считается: для
[2, 2, 3]ответ[3, 3, -1]. - Строго убывающий список даёт список из одних
-1.
Требование к сложности. Решение должно работать за O(n): вложенный перебор всех пар не подходит.
заготовка решения
def next_greater(nums: list[int]) -> list[int]:
# ваш код
pass