【また2ポインタ法】leetcode解いていたらいきなり機械学習問題出たかと思った

目次

解いた問題
学び
最初の解法
答え
感想

解いた問題

LeetCode 121 Best Time to Buy and Sell Stock
株取引を考えて利益が最大どのくらい出るかを答えてねってやつ

株価予測？機械学習？と思ったが、株価を模したリストが与えられて、それが時系列に並んでいるって想定で解く問題だった。

学び

• 2ポインタ法は結構汎用性のあるアルゴリズム
• 空間計算量の計算方法を理解した
• min,maxなんてものがあるのか（無知

最初に考えた解法

2ポインタ法を応用して、購入額と売却額を比較する方法を思いついた。

first.py

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy_price = prices[0] # 購入額のポインタ
        result = 0
        for i in range(1, len(prices)):
            if prices[i] < buy_price: # prices[i]が売却額のポインタ
                buy_price = prices[i]
            else:
                result = prices[i] - buy_price
        return result

行けたかな？と思ったがNG

出力が3であるから、利益が出そうなタイミング(prices[i] >= buy_priceのとき)はelseが絶対動いてしまうことに気づく。
上記のresultを別変数で保持しながらその最大値をresultで持つように変更。

second.py

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy_price = prices[0]
        result = 0
        pre_max = 0
        for i in range(1, len(prices)):
            if prices[i] < buy_price:
                buy_price = prices[i]
            else:
                pre_max = prices[i] - buy_price
                if result < pre_max:
                    result = pre_max
        return result

正解！いえ～～～～～い

ただ空間計算量が悪そう。

どうやって空間計算量って計算するんだろうか？
調べてみた。

答え

ChatGPT曰く最適解は下記。

answer.py

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = prices[0]
        max_profit = 0
        for p in prices[1:]:
            # その時点で売った場合の利益を評価
            max_profit = max(max_profit, p - min_price)
            # 以降に備えて最安値を更新
            min_price = min(min_price, p)
        return max_profit

最適解との違いはmax等の関数を使っているかの差。
一度に計算をすることでコード数を減らし洗練された印象がある。

ただ俺が書いたコードも空間計算量は$O(1)$となっているらしく、決して容量を食うものではないらしい。
空間計算量は「入力サイズに対して追加で必要になるメモリ量」を定量的に表したものだから、変数の個数が定数、もしくは入力によらないものだとすべて$O(1)$になる。

$O(n)$とかは、入力をnとしてfor文の中でlists.append(n*2)とかを繰り返したときらしい。

感想

ギブアップすることが減ってきて成長を感じる。

どんどん行こう（慢心