Online Stock Span

Средняя№901цена и размах

Нужно написать класс, который получает цену акции по одному дню. Каждый вызов next(price) возвращает размах сегодняшнего дня: сколько дней подряд, считая назад от сегодня и включая его, цена была не выше сегодняшней. Наш пример: next(7), next(3), next(4), next(4), next(2), next(9) возвращают 1, 1, 2, 3, 1, 6.

901 Online Stock SpanРазбор · 1×

Пример: next(7), next(3), next(4), next(4), next(2), next(9). Сверху цены по дням; в стеке пары (цена, размах), и каждый прошлый день входит ровно в одну из них.

012345ценыstackpricespan—
цены ещё нетсегодняхранится в паре в стекепроверяемая верхняя парав размахе сегодня

Создаём StockSpanner(): init выполняется один раз

01/42
сначала · назад · пуск · шаг
Скорость
1class StockSpanner:
2 function init():
3 stack = empty stack // pairs (price, span)
4 function next(price):
5 span = 1
6 while stack not empty and top.price <= price:
7 span = span + (pop from stack).span
8 push (price, span) onto stack
9 return span
состояние
stack
–
price
–
span
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Снятая пара не выше сегодняшнего дня, и все её дни тоже: они не выше её цены. Поэтому размах сегодня забирает их все сразу.
  2. Цены в стеке растут к низу: пару не выше сняли бы. Первая более высокая пара кончает размах, а под неё не заглянуть.
  3. Снятый день больше не нужен: сегодняшний не ниже и ближе, поэтому любой следующий день остановится на сегодняшнем или пройдёт оба.

Сложность

Каждый next в среднем O(1): каждая цена кладётся один раз и снимается не больше одного раза, поэтому n вызовов делают всего не больше 2n шагов со стеком. Память O(n) на стек.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.