Best Time to Buy and Sell Stock

Лёгкая№121самая низкая цена

Даны цены акции по дням. Купи её в один день и продай в какой-то более поздний, один раз. Верни наибольшую прибыль, какую можно получить, или 0, если любая сделка в минус. Наш пример: [4, 10, 7, 2, 9, 1, 3] — ответ 7: купить по 2 в день 3, продать по 9 в день 4.

121 Best Time to Buy and Sell StockРазбор · 1×

Пример: [4, 10, 7, 2, 9, 1, 3]. Смотрите на день 3: цена падает до 2, когда прибыль 6 уже найдена; продажа по 9 на следующий день её обгоняет.

ценаlowbest0411027324951634
этот шагдень, в который куплено по lowберём отсюдаответ: покупка и продажа

День 0: купить пока можно только по 4, low = 4

01/27
сначала · назад · пуск · шаг
Скорость
1function maxProfit(prices):
2 low = prices[0] // lowest price so far
3 best = 0
4 for i from 1 to len(prices) - 1:
5 profit = prices[i] - low // sell today
6 best = max(best, profit)
7 low = min(low, prices[i])
8 return best
состояние
i
–
low
4
profit
–
best
–
историянажмите шаг, чтобы вернуться

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

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

  1. Если продать в день i, лучше всего купить по самой низкой цене до него. Именно её хранит low, поэтому каждый день — одно вычитание, а не просмотр всех прошлых дней.
  2. Новый минимум не стирает best: прошлая продажа остаётся настоящей сделкой. Здесь best хранит 6, пока low падает до 2, и заменяет его только продажа по 9.
  3. Ответ — не самая высокая цена минус самая низкая: продать можно только после покупки. 10 идёт раньше 2, а после 1 цена не поднимается выше 3.

Сложность

Время O(n): один проход по дням, на каждый день постоянная работа. Память O(1): только low и best; строки на рисунке показывают их историю.

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

Решить на LeetCode ↗

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