Почему это работает
- Если продать в день i, лучше всего купить по самой низкой цене до него. Именно её хранит low, поэтому каждый день — одно вычитание, а не просмотр всех прошлых дней.
- Новый минимум не стирает best: прошлая продажа остаётся настоящей сделкой. Здесь best хранит 6, пока low падает до 2, и заменяет его только продажа по 9.
- Ответ — не самая высокая цена минус самая низкая: продать можно только после покупки. 10 идёт раньше 2, а после 1 цена не поднимается выше 3.
Сложность
Время O(n): один проход по дням, на каждый день постоянная работа. Память O(1): только low и best; строки на рисунке показывают их историю.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗