Лучшее время для покупки и продажи акций
Дан целочисленный массив prices, где prices[i] — это цена NeetCoin в i-й день.
Вы можете выбрать один день для покупки одного NeetCoin и выбрать другой день в будущем для его продажи.
Верните максимальную прибыль, которую вы можете получить. Если вы решите не совершать никаких транзакций, прибыль будет равна 0.
Пример 1:
Input: prices = [7,1,5,3,6,4]
Output: 5
Объяснение: Покупка во 2-й день (цена = 1) и продажа в 5-й день (цена = 6), прибыль = 6-1 = 5.
Пример 2:
Input: prices = [7,6,4,3,1]
Output: 0
Объяснение: В этом случае лучше не совершать никаких транзакций, прибыль = 0.
Рекомендуемая временная и пространственная сложность
Вам следует стремиться к решению с временной сложностью O(n) и пространственной сложностью O(1), где n — размер входного массива.
Подсказка 1
Попробуйте отслеживать минимальную цену, которую вы видели до текущего момента. Это поможет найти максимальную прибыль.
Подсказка 2
На каждом шаге вы можете обновлять минимальную цену и проверять, не даст ли продажа по текущей цене большую прибыль.