【海外エンジニア転職 Coding Interview鍛錬】LeetCode121. Best Time to Buy and Sell Stock
こんにちは脳筋ニシキです！
今回はこちらで紹介したLeetCode75選（Blind75）から１問（easy）選んで解いていきたいと思います！
atsashimipy.hatenablog.com
今日解いていくのはこちらの問題
やること
"prices"として渡されたとある銘柄の株の値動き表した配列から、一度づつの売買で最高益を返す。
prices[i] は、この銘柄のi日目の価格
条件
1 <= prices.length <= 10^5
0 <= prices[i] <= 10^4
例
Input: prices = [7,1,5,3,6,4]
Output: 5
この条件下で最高益は
価格が１の時に買い、６の時に売って得られる５。
カテゴリ
Arrays
考え方
とりあえず現実世界と同じで一番安い時に買って、一番高い時に売る！
ここで大事なのは買った時の値段と売った時の値段、そしてその差のから生まれる利益。
利益 = 売値 - 買値
0日目からN日目までの利益の動きをチェックしつつ、できるだけO(N)で解いていきたい。
上の例を見て考えてみる。
その日時点での一番の買い時（最安値）と最高益に注意しながら
０日目から見ていく。
prices = [7,1,5,3,6,4]
０日目:価格７ 初日で比べる対象がないので、最安値=７ 最高益=0
１日目:価格１ 前日の７より安いので、この時点での最安値=１に更新 最高益=0 のまま
２日目:価格５ 利益は５−１で４で現時点での最高益 最安値=１のままで 最高益=４に更新
３日目:価格３ 利益は３−１で２出ているが最高益でないので 最安値=１ 最高益=４のまま
４日目:価格６ 利益は６−１で５最高益を更新 最安値=１のままで、最高益=５に更新
５日目:価格４ 利益は４−１で３ 最安値=１ 最高益=５のまま
こうして最高益 = ５が確定される。
ではこの考え方をもとに
早速codeしていく！
class Solution: def maxProfit(self, prices: List[int]) -> int:
まず特殊ケースを対処。
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) == 1: return 0
思いつくのは与えられた配列の長さが１の時。
つまり０日目で終わってる時、これは価格がどうあろうと最高益は０。というか取引できない。
問題文にも利益が出ないときは０を返せと書いてある。
If you cannot achieve any profit, return 0
次に買う日&売る日の初期値（２ポインター）と現時点での利益を設定する。
買う日と売る日は別々でないといけないので、
買う日を０日目
売る日を１日目
最高益を０
とする。
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) == 1: return 0 buy = 0 sell = 1 profit = 0
そして、この２つのポインターを上で考えたように
while loop で１日ずつ価格の変動と現在の利益（売値–買値）をチェックしていく。
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) == 1: return 0 buy = 0 sell = 1 profit = 0 while sell < len(prices): curr_profit = (prices[sell] - prices[buy])
もし現在の時点で利益がマイナスだった場合。
それはつまり最安値が更新されたということ。
なのでこの価格で買うのが現状ベスト。
ということで”buy”ポインターをこの日に移動。
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) == 1: return 0 buy = 0 sell = 1 profit = 0 while sell < len(prices): curr_profit = (prices[sell] - prices[buy]) if curr_profit <= 0: buy = sell
そして次は
もし現在の時点で利益がプラスだった場合。
それはつまり最高益が更新された可能性があるということ。
なので今までの最高益の値と今回の利益を比べて、大きい方を新たな最高益と再設定。
lass Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 1:
return 0
buy = 0
sell = 1
profit = 0
while sell < len(prices):
curr_profit = (prices[sell] - prices[buy])
if curr_profit <= 0:
buy = sell
else:
profit = max(profit, curr_profit)
そして１日の価格をチェックし終えたら次の日を調べるため”sell”ポインターを一つ次に進めます。
lass Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 1:
return 0
buy = 0
sell = 1
profit = 0
while sell < len(prices):
curr_profit = (prices[sell] - prices[buy])
if curr_profit <= 0:
buy = sell
else:
profit = max(profit, curr_profit)
sell += 1
とこんな感じで書いていくと、あとは勝手にpythonさんがやってくれるので、
while loop が終わったらあとはprofitを返すだけ。
そうするとこんな感じになります。
解答例
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) == 1: return 0 buy = 0 sell = 1 profit = 0 while sell < len(prices): curr_profit = (prices[sell] - prices[buy]) if curr_profit <= 0: buy = sell else: profit = max(profit, curr_profit) sell += 1 return profit
Complexity Analysis
Time complexity: O(n)
与えられた長さnの配列を一巡するだけ
Space complexity: O(1)
３つの変数（buy, sell, profit）
自分の考えを文字に起こすと理解が深まっていいな！
ただ、伝わりづらい部分も多々あると思うので、ご意見、感想、アドバイスお待ちしています！
それではまた次のLeetCodeの問題でお会いしましょう！
