[LeetCode解法] 121. Best Time to Buy and Sell Stock

問題の説明

Best Time to Buy and Sell Stock

一度だけ株を買って売ることで得られる最大の利益を計算します。

解法

アプローチ

一度だけ株を買って売る場合の最大の利益を求めるには、株価の最低点と最高点の差を計算する必要があります。与えられたリストが時系列順に並んでいるため、価格をイテレートする際にこれを考慮する必要があります。

アルゴリズムは単純で、コードで直接説明します。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0                # 初期利益は0
        lower = 100000            # 最初の最低点を与えられたテストケースで最大の値に設定します。
        for v in prices:
            if v < lower:         # 最低点を更新
                lower = v
            if v - lower > 0 and profit < v - lower:    # 現在の値と最低点の差が利益よりも大きい場合は、利益を更新します。
                profit = v - lower
        return profit             # 最後のループ後に残った利益が最大の利益です。

この解法の時間複雑度と空間複雑度は次のとおりです。

• 時間複雑度：O(N)
  • pricesをループするため、時間複雑度はO(N)です。
• 空間複雑度：O(1)
  • 追加のスペースは使用されていません。