Сложность: 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⃣Добавить текущую цену и размах на вершину стека.
Вернуть текущий размах.
😎 Решение:
using System;
using System.Collections.Generic;
public class StockSpanner {
private Stack<Tuple<int, int>> stack;
public StockSpanner() {
stack = new Stack<Tuple<int, int>>();
}
public int Next(int price) {
int span = 1;
while (stack.Count > 0 && stack.Peek().Item1 <= price) {
span += stack.Pop().Item2;
}
stack.Push(Tuple.Create(price, span));
return span;
}
}
Ставь 👍 и забирай 📚 Базу знаний