Сложность: medium
Разработайте алгоритм, который собирает ежедневные котировки цен на некоторые акции и возвращает размах цены этой акции за текущий день. Размах цены акции за один день - это максимальное количество дней подряд (начиная с этого дня и в обратном направлении), в течение которых цена акции была меньше или равна цене этого дня.
Например, если цены акции за последние четыре дня равны [7,2,1,2], а цена акции сегодня равна 2, то размах сегодняшнего дня равен 4, поскольку, начиная с сегодняшнего дня, цена акции была меньше или равна 2 в течение 4 дней подряд.
Также, если цена акции за последние четыре дня равна [7,34,1,2], а цена акции сегодня равна 8, то размах сегодняшнего дня равен 3, так как начиная с сегодняшнего дня цена акции была меньше или равна 8 в течение 3 дней подряд. Реализация класса StockSpanner: StockSpanner() Инициализирует объект класса. int next(int price) Возвращает размах цены акции, учитывая, что сегодняшняя цена равна price.
Пример:
Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]
👨💻 Алгоритм:
1⃣Инициализировать стек для хранения пар значений (цена, размах) и переменную для текущего индекса.
2⃣Для метода next:
Установить начальный размах текущего дня равным 1.
Пока стек не пуст и верхний элемент стека имеет цену меньше или равную текущей цене:
Добавить размах верхнего элемента стека к текущему размаху.
Удалить верхний элемент стека.
3⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.
😎 Решение:
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price):
span = 1
while self.stack and self.stack[-1][0] <= price:
span += self.stack.pop()[1]
self.stack.append((price, span))
return span
Ставь 👍 и забирай 📚 Базу знаний