Stock Span Problem
Для каждого дня вам дана цена закрытия акции: prices[i] — цена акции в день i. Период для дня i — это количество последовательных дней, заканчивающихся днем i и включая его, в течение которых цена была меньше или равна prices[i].
Верните периоды для каждого дня в том же порядке, что и prices. Каждый период не меньше 1, потому что день всегда учитывается сам.
Функция
- pricesinteger-array
- цена за каждый день по порядку
- Возвращаетinteger-array
- период каждого дня, в том же порядке
Ограничения
1 ≤ prices.length ≤ 1041 ≤ prices[i] ≤ 105- Более ранний день с такой же ценой учитывается в диапазоне; только строго более высокая цена прерывает его.
Примеры
- Ввод
- prices = [31, 27, 14, 21, 30, 18, 40]
- Вывод
- [1, 1, 1, 2, 4, 1, 7]
- Пояснение
- День 3 на отметке 21 возвращается назад через 14 и останавливается на 27: диапазон 2. День 4 на отметке 30 останавливается на 31: диапазон 4. День 6 на отметке 40 превосходит все предыдущие цены и охватывает все 7 дней.
- Ввод
- prices = [8, 8, 3, 8]
- Вывод
- [1, 2, 1, 4]
- Пояснение
- Одинаковые цены учитываются, поэтому цена 8 в день 1 покрывает день 0 и получает 2. Цена 8 в день 3 покрывает день 3 и оба предыдущих дня с ценой 8 — всего 4.
- Ввод
- prices = [50, 40, 30, 20]
- Вывод
- [1, 1, 1, 1]
- Пояснение
- Каждый день дешевле предыдущего, поэтому ни один промежуток не охватывает дни до самого этого дня, и каждый промежуток равен 1.
Дополнительный вопрос
Теперь цены поступают по одной, и вы должны сообщать о каждом промежутке по мере поступления цены. Какой подход по-прежнему работает и что он сохраняет между вызовами?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Обратный отсчёт от каждого дня повторяет работу: при 8000 днях с одной и той же ценой в последний день придётся вернуться на 8000 дней назад. Если идти назад от сегодняшнего дня, какие более ранние дни можно навсегда пропустить?
Как только цена сегодня становится не ниже цены в какой-либо предыдущий день, этот предыдущий день уже никогда не сможет стать тем днём, который остановит более поздний интервал: сегодняшний день ближе и стоит не меньше. Важны только дни, цена в которые выше, чем во все последующие дни, и их цены убывают от самых старых к самым новым.
Проходи по дням по порядку и храни на стеке индексы предыдущих дней, которые всё ещё важны. Прежде чем дать ответ для сегодняшнего дня, удаляй из стека все дни, цена которых не выше сегодняшней. Пустой стек означает, что интервал начинается с дня 0; в противном случае он заканчивается за день до дня, оставшегося на вершине. Затем добавь сегодняшний день в стек.
Решение
Интервал дня заканчивается в ближайший предыдущий день со строго более высокой ценой. Чтобы найти его, нужно пройти назад до n шагов для каждого дня. Вместо этого сохраняй только дни, которые ещё могут ограничить будущий интервал: стек индексов со строго убывающими ценами позволяет найти все границы за один проход.
Считай в обратном порядке, начиная с любого дня
Верно, но не успевает на самых больших тестах
Идея
Следуй определению. Для дня i отступай на один день назад, пока цена в этот день не выше prices[i], включая сам день i. Первый день с ценой строго выше или начало массива завершают проход.
Каждый проход заново просматривает предыдущие дни. При неизменных или растущих ценах каждый проход доходит до дня 0: для n = 10^4 дней это около 5 × 10^7 шагов.
Алгоритм
- Создай
span— массив той же длины, что иprices. - Для каждого дня
iустанови счётчик на 0, а указательj— наi. - Пока
j ≥ 0иprices[j] ≤ prices[i], увеличивай счётчик на 1 и перемещайjна один день назад. - Сохрани счётчик в
span[i]. После последнего дня верниspan.
def stockSpan(prices):
span = []
for i in range(len(prices)):
count = 0
j = i
# Count today and every earlier day in a row that is not more expensive.
while j >= 0 and prices[j] <= prices[i]:
count += 1
j -= 1
span.append(count)
return spanМонотонный стек более высоких дней
Идея
Назовём блокирующим ближайший предыдущий день, цена в который строго выше. Ширина диапазона — today - blocker или today + 1, если такого дня нет.
В первом примере день 3 стоит 21, а день 4 — 30. Любой последующий проход сначала достигает дня 4, а любая цена, которая преодолевает 30, преодолевает и 21, поэтому день 3 больше никогда не сможет блокировать. В общем случае, когда наступает сегодняшний день, каждый предыдущий кандидат с ценой не выше сегодняшней уже не нужен: удаляем его из стека. День, оставшийся наверху, — блокирующий для сегодняшнего дня. Затем добавляем в стек сегодняшний день.
Цены в стеке строго убывают от низа к верху, поэтому первый оставшийся элемент — ближайшая более высокая цена. В первом примере день 4 удаляет дни 3 и 1 и останавливается на дне 0; ширина диапазона равна 4 - 0 = 4. Каждый день добавляется в стек один раз и удаляется не более одного раза, поэтому проход выполняется за O(n).
Алгоритм
- Создайте массив
spanи пустой стек для индексов дней. - Для каждого дня
todayизвлекайте индексы из стека, пока их цена меньше или равнаprices[today]. - Если стек пуст, то span равен
today + 1; в противном случае он равенtodayминус индекс на вершине стека. - Добавьте
todayв стек и перейдите к следующему дню. Вернитеspan.
def stockSpan(prices):
span = [0] * len(prices)
higher = [] # indices of earlier days, prices strictly falling toward the top
for today, price in enumerate(prices):
# A day that is not more expensive than today can never stop a later span.
while higher and prices[higher[-1]] <= price:
higher.pop()
# The span reaches back to the nearest more expensive day, or to day 0.
span[today] = today - higher[-1] if higher else today + 1
higher.append(today)
return span
Ловушки и крайние случаи
- Удаление из стека при
<вместо<=. В[8, 8, 3, 8]последний день имеет интервал 4; остановка на предыдущем 8 даёт 2. - Запись
todayвместоtoday + 1, когда стек пуст. День 0 должен получить 1, а не 0. - Удаление из стека только один раз в день. В первом примере 40 должно устранить дни 5, 4 и 0. Если остановиться после дня 5, день 4 будет выглядеть как его блокирующий элемент, а интервал составит 2 вместо 7.
- В Lua и R массивы начинаются с 1. При индексации с 1 интервал для пустого стека равен
today, а неtoday + 1.
Частые вопросы4
Какова временная сложность задачи о диапазоне цен акций?
Время O(n) и дополнительная память O(n) при использовании монотонного стека, поскольку каждый день покидает стек не более одного раза. Проход с конца для каждого дня занимает O(n²), когда цены продолжают расти или остаются неизменными.
В стеке должны храниться цены или индексы дней?
Индексы дней. Интервал — это количество дней, и только индекс блокировщика позволяет его получить. prices[index] считывает цену для сравнения.
Можно ли решить задачу о биржевом диапазоне без отдельного стека?
Да. Начни с j = today - 1; пока j ≥ 0 и prices[j] ≤ prices[today], переходи к j - span[j], поскольку цена каждого дня внутри этого интервала не превышает prices[j]. Интервал равен today - j. Переходы приводят только к дням, которые оставались бы в стеке, поэтому проход занимает O(n).
Является ли задача о диапазоне цен акций задачей о предыдущем большем элементе?
Да, измеряется в днях: для каждого дня найди ближайший предыдущий день, когда цена была строго выше, и укажи, насколько далеко он находится. Измени направление прохода или условие сравнения — и тот же стек даст следующий больший, следующий меньший или предыдущий меньший элемент.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def stockSpan(prices):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргумент
prices = [31, 27, 14, 21, 30, 18, 40]
Ожидаемый вывод
[1, 1, 1, 2, 4, 1, 7]