Описание испытания
Вам дан массив prices
, где prices[i]
— цена данной акции на ith
день.
Вы хотите максимизировать свою прибыль, выбрав один день для покупки одной акции и выбрав другой день в будущем для продажи этой акции.
Возвратите максимальную прибыль, которую вы можете получить от этой транзакции. Если вы не можете получить прибыль, верните 0.
Пример 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Пример 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Первое решение (временная сложностьO(n²)):
var maxProfit = function (prices) { let margin = 0; for (i = prices.length - 1; i > 0; i--) { for (k = 0; k < i; k++) { if (prices[i] - prices[k] > margin) { margin = prices[i] - prices[k]; } } } return margin; };
Временная сложность данного кода равна O(n²), где n — длина входного массива prices
. Код использует структуру вложенного цикла для сравнения каждой пары цен и расчета максимальной прибыли. Внешний цикл повторяется от prices.length - 1
до 1, а внутренний цикл повторяется от 0 до i
.
Для каждой пары цен код проверяет, превышает ли разница между prices[i]
и prices[k]
текущую margin
. Если это так, margin
обновляется.
ПРИМЕЧАНИЕ. Этой наихудшей временной сложности можно избежать, используя один цикл. Другое решение приведено ниже:
Второе решение (временная сложностьO(n)):
var maxProfit = function (prices) { let leftIndex = 0, rightIndex = 1, maxMargin = 0; while (rightIndex < prices.length) { if (prices[leftIndex] < prices[rightIndex]) { let profit = prices[rightIndex] - prices[leftIndex]; maxMargin = Math.max(maxMargin, profit); } else { leftIndex = rightIndex; } rightIndex++; } return maxMargin; };
Временная сложность обновленного кода равна O(n), где n — длина входного массива prices
.
В коде используется один цикл, который перебирает массив prices
слева направо. Он поддерживает два индекса, leftIndex
и rightIndex
, которые представляют начальную и конечную точки окна потенциальной прибыли. Изначально для leftIndex
установлено значение 0, а для rightIndex
установлено значение 1.
На каждой итерации код проверяет, превышает ли цена rightIndex
цену leftIndex
. Если это так, он рассчитывает прибыль, вычитая цену leftIndex
из цены rightIndex
. Затем код обновляет maxMargin
максимальным значением между текущим maxMargin
и рассчитанной прибылью.
Если цена на rightIndex
не выше цены на leftIndex
, это означает, что открытие нового окна прибыли с текущей позиции приведет к меньшей прибыли. В этом случае код обновляет leftIndex
до rightIndex
, чтобы открыть новое окно потенциальной прибыли.
Цикл продолжается до тех пор, пока rightIndex
не достигнет конца массива prices
.
Удачного кодирования!!