Сегодняшний вопрос — еще один простой вопрос с тегами от leetcode. Давайте перейдем к проблеме, не теряя много времени.

121. Лучшее время для покупки и продажи акций

Допустим, у вас есть массив, в котором i-й элемент — это цена данной акции в день i.

Если бы вам было разрешено совершить не более одной сделки (т. е. купить одну и продать одну акцию), разработайте алгоритм для нахождения максимальной прибыли.

Обратите внимание, что вы не можете продать акцию до того, как купите ее.

Пример 1:

Input: [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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Пример 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction, hence max profit = 0.

Один из способов решить данную проблему — найти прибыль, рассмотрев все варианты покупки и продажи. Как мы это делаем?

Рассмотрим первое число как вариант покупки. Рассматривайте все числа после покупки как варианты продажи.
Найдите разницу между стоимостью продажи и стоимостью покупки. Полученная прибыль будет положительным числом. Если мы не получили положительного числа, возвращаем 0.
Максимум полученной прибыли - это наш результат.

class MaxProfitFinder:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for first in range(len(prices)):
            for second in range(first+1, len(prices)):
                profit = max(profit, prices[second] - prices[first])
        return profit

Анализ сложности

Временная сложность

У нас есть два цикла for, которые дважды обходят весь список цен. Следовательно, временная сложность равна O(N²), где N — длина прайс-листа.

Космическая сложность

Мы не используем никакого дополнительного пространства при реализации алгоритма, и, следовательно, сложность пространства составляет O (1).

Как мы должны улучшить временную сложность?

Можем ли мы попробовать реализовать решение с помощью одного прохода?

Инициализируйте стоимость покупки как бесконечность, а полученную прибыль как 0.

Пройдитесь по каждому значению, проверьте, меньше ли текущее значение, чем купить. Если да, то текущее число будет стоимостью покупки.

Если нет, проверьте, не превышает ли разница между текущей стоимостью и стоимостью покупки прибыль. Если да, то разница между текущим числом и стоимостью покупки и есть наша прибыль.

class MaxProfitFinder:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        profit = 0
        for i in range(len(prices)):
            if prices[i] < min_price:
                min_price = prices[i]
            else:
                profit = max(profit, prices[i] - min_price)
        return profit

Анализ сложности

Временная сложность

У нас есть один цикл for, который проходит через весь список цен. Следовательно, временная сложность равна O(N), где N — длина прайс-листа.

Космическая сложность

Мы не используем никакого дополнительного пространства при реализации алгоритма, и, следовательно, сложность пространства составляет O (1).

Буду рад услышать ваше мнение о моих публикациях. Дайте мне знать, если у вас есть какие-либо комментарии или отзывы.