【LeetCode】 121. Best Time to Buy and Sell Stock 解答・解説【Python】

はじめに
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, brute force
  2. 解答2：Python, two pointer
終わりに

はじめに

ポイント

two poinerを使用

この記事で得られるもの

two pointerの初歩的な使い方
時間計算量の改善に関する考え方

この記事が役立ちそうな方

two pointerの練習をしたい方
全探索(brute force)以外の解き方に触れたい方

詳細

問題

原文

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

1
2
3
4

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.

1
2
3

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

1 <= prices.length <= 10⁵

0 <= prices[i] <= 10⁴

内容(和訳)

i番目の要素がi日目の株価である配列pricesが与えられます。

ある日を選んで株を購入し、将来の別の日を選んで株を売却することで利益を最大化したいです。

最大利益を得られる取引日を返してください。

存在しない場合は0を返してください。

※正しくない可能性があります。

解答

解答1：Python, brute force

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        answer = 0
        for i in range(len(prices)):
            for j in range(i, len(prices)):
                answer = max(answer, prices[j] - prices[i])
        return answer

class Solution:

def maxProfit(self, prices: List[int]) -> int:

answer = 0

for i in range(len(prices)):

for j in range(i, len(prices)):

answer = max(answer, prices[j] - prices[i])

return answer

この解答はtime limit exceededとなります。

pricesの要素数は最大10^5個あることが問題文のconstraints(制約)に記載されています。

10^10回の時間計算量となり、時間切れとなるようです。

解答2：Python, two pointer

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        left = 0
        right = 1
        answer = 0

        #rightポインタが配列の右端に辿り着くまで繰り返す
        while right < len(prices):
            #右側の価格が左側の価格より大きい場合
            if prices[right] > prices[left]:
                #answerに、answerと(右側の価格 - 左側の価格)の大きい方を代入
                answer = max(answer, prices[right] - prices[left])
            #右側の価格が左側の価格より小さい場合
            else:
                #左側のポインタを右側と同じ場所まで進める
                left = right
            #右側のポインタを1つ進める
            right += 1
        
        return answer

class Solution:

def maxProfit(self, prices: List[int]) -> int:

left = 0

right = 1

answer = 0

#rightポインタが配列の右端に辿り着くまで繰り返す

while right < len(prices):

#右側の価格が左側の価格より大きい場合

if prices[right] > prices[left]:

#answerに、answerと(右側の価格 - 左側の価格)の大きい方を代入

answer = max(answer, prices[right] - prices[left])

#右側の価格が左側の価格より小さい場合

else:

#左側のポインタを右側と同じ場所まで進める

left = right

#右側のポインタを1つ進める

right += 1

return answer

two pointerアルゴリズムを使用します。

配列内で2つのインデックスを使って進めていきます。

今回の問題では、右と左の2つのインデックス(pointer)を用意し、

右の方が大きければ最大値との値を比較して大きい方を取り入れ、

左の方が大きければ、右と同じ場所までインデックスを進めることで、

解答1よりも効率よく探索しています。

解答1では配列pricesを全探索で2周しなければなりませんが、

こちらの解答では1周で済むので、時間計算量がO(n)に改善できます。

終わりに

補足・参考・感想

Atcoderだと、10^8を超える時間計算量だと制限時間切れとなったように思います。

LeetCodeでは正確な制限時間がわからないですが、今までの解いた感覚から近いように思います。

どこかに書いてあるかもしれないので、いずれ調べてみたいと思います。

疑問が解決した方はこちらへ

前：350. Intersection of Two Arrays II

次：21. Merge Two Sorted Lists

LeetCode 解答・解説記事一覧

疑問が解決しない方はこちらへ

他のtwo pointerの問題をこちらに集めています。

テーマごとに集中して問題を解きたいときにも役立ちます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類