LeetCode — 121. Лучшее время для покупки и продажи акций. DSA #3 Объяснение.


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

Легко

Ссылка на вопрос

Код

Python || C++ || TypeScript

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

Например, если у нас есть цены [1, 2, 3, 4, 5], то мы можем купить акции по цене 1 и продать их по цене 5, прибыль составит 4.

Аналогично, если у нас есть цены [7, 1, 5, 3, 6, 4], то мы можем купить акции по цене 1 и продать их по цене 6, прибыль составит 5.

А если у нас цены [7, 6, 4, 3, 1], то мы не можем получить никакой прибыли.

Давайте сначала обсудим подход грубой силы.

Подход грубой силы

  • Мы покупаем акции в первый день
  • Рассчитываем всю прибыль, которую мы можем получить, продавая ее в каждый день, то есть мы продаем ее в день 2 и сохраняем прибыль, затем мы продаем ее в день 3 и сохраняем прибыль и так далее.
  • Повторите эти два пункта для всех дней.
  • Верните максимальную прибыль, которую мы можем получить.

Мы можем описать вышеуказанный подход, используя два цикла for.

Код

def bestTimeForStockMethod1(prices: list[int]) -> int:
    max_profit = 0
    for buy_index, buy_value in enumerate(prices):
        for sell_index in range(buy_index + 1, len(prices)):
            curr_profit = prices[sell_index] - buy_value
            max_profit = max(max_profit, curr_profit)
    return max_profit
Войти в полноэкранный режим Выйти из полноэкранного режима

Давайте разберемся в приведенном выше коде на примере.

prices = [7, 1, 5, 3, 6, 4]

—> Первая итерация

Мы покупаем акции в первый день, т.е. покупаем акции по цене 7.

  • Мы продаем акции во второй день, т.е. продаем акции по цене 1.
  • Прибыль составляет 1 - 7 = -6, т.е. мы в убытке.
  • Мы обновляем max_profit.
  • Мы продаем акции в день 3, т.е. продаем акции по цене 5.
  • Прибыль составляет 5 - 7 = -2, т.е. мы в убытке.
  • Мы обновляем значение max_profit.
  • ………continues…………………….
  • Мы продаем акции в день 6, т.е. продаем акции по цене 4.
  • Прибыль составляет 4 - 7 = -3, т.е. мы в убытке.
  • Мы обновляем max_profit.

—> Вторая итерация

Мы покупаем акции на второй день, т.е. покупаем акции по цене 1.

  • Мы продаем акции на третий день, т.е. продаем акции по цене 5.
  • Прибыль составляет 5 - 1 = 4, т.е. мы в прибыли.
  • Мы обновляем max_profit.

И так далее.

В конце у нас будет максимальная прибыль, которую мы можем получить.

Time Complexity: O(n^2)

Лучший подход

prices = [7, 1, 5, 3, 6, 4]

Как и в предыдущем случае, давайте купим акции в день 1, т.е. по цене 7.

Теперь, когда мы продадим акции в день 2, т.е. по цене 1, мы получим прибыль 1 - 7 = -6.

И на основании этого убытка мы можем сказать, что цена акции в день 2 меньше, чем цена акции в день 1.
Так почему же мы покупаем акции в день 1? Давайте купим акции в день 2, то есть по цене 1. Поэтому мы переместим
наш указатель на день 2, т.е. на цену 1.

Теперь, когда мы продадим акции в день 3, т.е. по цене 5, мы получим прибыль 5 - 1 = 4.

Теперь мы продадим акции в день 4, т.е. по цене 3.
Мы получим прибыль 3 - 1 = 2. Мы сохраним максимальную прибыль, т.е. 4.

Теперь мы продадим акции на пятый день, т.е. по цене 6.
Мы получим прибыль 6 - 1 = 5. Мы сохраним максимальную прибыль, т.е. 5.

Теперь мы продадим акции на 6-й день, т.е. по цене 4.
Мы получим прибыль 4 - 1 = 3. Мы сохраним максимальную прибыль, т.е. 5.

Теперь мы находимся в конце цикла, и поскольку мы не столкнулись с убытками, это означает, что мы купили акции по минимально возможной цене.
Следовательно, max_profit, которое мы сохраняем, — это максимальная прибыль, которую мы можем получить.

Рассмотрим другой пример, но с меньшим количеством английских слов.

prices = [7, 2, 5, 6, 1, 4]

Пусть у нас есть два указателя

[7,     2, 5, 6, 1, 4]
 |      |
 Buy    sell

 2 - 7 = -5 
 Loss which means we can buy stock at lower price 
 therefore we move our buy pointer to sell pointer and increase sell pointer by 1

[7, 2,     5, 6, 1, 4]
 |         |
 buy       sell

5 - 2 = 3    max_profit = 3

[7, 2,     5, 6, 1, 4]
    |         |
    buy      sell

6 - 2 = 4    max_profit = 4

[7, 2,  5, 6, 1, 4]
    |         |
    buy      sell

1 - 2 = -1   max_profit = 4

Loss which means we can buy stock at lower price 
therefore we move our buy pointer to sell pointer and increase sell pointer by 1

[7, 2,  5, 6, 1,    4]
              |     |
              buy   sell

4 - 1 = 3    max_profit = 4

we are at the end of the loop. Therefore, we return max_profit i.e 4

Войти в полноэкранный режим Выйти из полноэкранного режима

Time Complexity: O(n)

Код

Мы можем закодировать это, используя подход с двумя указателями.

def bestTimeForStockMethod2(prices: list[int]) -> int:
    max_profit = 0
    buy, sell = 0, 1
    while sell < len(prices):
        curr_profit = prices[sell] - prices[buy]
        if curr_profit < 0:
            buy = sell
        max_profit = max(max_profit, curr_profit)
        sell += 1
    return max_profit
Вход в полноэкранный режим Выйти из полноэкранного режима

Оцените статью
devanswers.ru
Добавить комментарий