目次
解いた問題
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)とかを繰り返したときらしい。
感想
ギブアップすることが減ってきて成長を感じる。
どんどん行こう（慢心