Difficulty: Easy Language: JavaScript
описание проблемы
Вы задали массив цен, где цены[i] — это цена данной акции
на i-й день.
Вы хотите максимизировать свою прибыль, выбрав один день для покупки одной акции и выбрав другой день в будущем для продажи этой акции.
Верните максимальную прибыль, которую вы можете получить от этой сделки.
Если вы не можете получить никакой прибыли, верните 0.
Объяснение 1: Купить во второй день (цена = 1) и продать в пятый день (цена = 6), прибыль = 6–1 = 5. Не 7–1 = 6, поскольку цена продажи должна быть выше цены покупки.
Обратите внимание, что покупка во второй день и продажа в первый день не разрешены
, поскольку вы должны купить перед продажей.
Объяснение 2: В этом случае транзакции не выполняются, а максимальная прибыль = 0.
Решение грубой силы — O (n²)
Чтобы решить эту проблему, во-первых, мы используем подход алгоритм грубой силы. мы попробуем все возможные прибыли, которые мы можем получить от данных значений, и выберем самое высокое
Неудачная временная сложность: O(n²)
Входной размер равен 10⁵, поэтому вложенный цикл вызовет TLE (превышение ограничения по времени).
Лучшее решение — O(n)
Мы можем просмотреть все цены и вместо этого мы можем отслеживать минимальную цену и вычитать ее из цен продажи вот так.
Анализ сложности
Временная сложность: O(n)
Пространственная сложность: O(1)
Это решение отлично работает!
Исходный код :) https://github.com/codeXXripper/Leetcode-JS
Подпишитесь на меня, чтобы узнать больше
