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

はじめに
1. ポイント
詳細
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

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

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- 2ポインタ
- スライディングウインドウ

詳細

問題

原文

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

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.

1
2
3
4
5

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.

1
2
3
4

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

1
2
3

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

1 <= prices.length <= 3 * 10⁴

0 <= prices[i] <= 10⁴

内容(和訳)

i番目の要素がi日目の株価を示す整数配列pricesが与えられます。

各日で、株を買うか売るかを選ぶことができます。

同時に1つだけ保有することができます。

同じ日に株を買って売ることができます。

利益が最大となるように取引した場合の、最大利益を返してください。

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

考察

最大利益を返すためには、利益が最大となるような取引を考える必要がありそうです。

単純に最小の値と最大の値を見つけてその差を求める方法を試したいですが、

配列prices最大値と最小値の間に小さな株価の増減があり、

その利益を積み重ねて最大利益になるパターンもあるかもしれません。

株価の並びのパターンを考えてみます。

➀[1,2,3,4,5]のように増加し続ける場合

②[5,4,3,2,1]のように減少し続ける場合

③[1,2,4,2,5,]のように増減する場合

➀は最小値1と最大値5の差を取って返すこともできます。

また、1,2、2,3、3,4、4,5のように各日の利益を積み重ねて最大利益として返すこともできます。

②はそもそも利益を出すことができません。

③は単に1,5の差を取って返すだけでは不正解になりそうです。

※1,2、2,4、2,5と3回取引することで利益が5になる。

他にもあるかもしれませんが、これらのパターンをクリアできる必要がありそうです。

解答

解答1：Python, sliding window

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        #Initial variables right and left as index.
        #These have the value 0.
        left = 0
        right = 0
        #Assign the value 0 to the variable "sum_profit" which represents the sum of returns from each deal.
        sum_profit = 0
        
        #Start a for loop, iterate "i" over the range from 0 to length of "prices".
        for i in range(len(prices)):
            #Check if the element indexed by the variable "right" is bigger than the element indexed by the variable "left".
            if prices[right] > prices[left]:
                #If the condition is true, add the result of subtracting the two elements to the varibale "sum_profit".
                sum_profit += prices[right] - prices[left]
            #Proceed indexes.
            #left index has to start from right index in next iterate.
            #right index proceed each iterate.
            left = right
            right += 1
        #Return "sum_profit".
        return sum_profit

class Solution:

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

#Initial variables right and left as index.

#These have the value 0.

left = 0

right = 0

#Assign the value 0 to the variable "sum_profit" which represents the sum of returns from each deal.

sum_profit = 0

#Start a for loop, iterate "i" over the range from 0 to length of "prices".

for i in range(len(prices)):

#Check if the element indexed by the variable "right" is bigger than the element indexed by the variable "left".

if prices[right] > prices[left]:

#If the condition is true, add the result of subtracting the two elements to the varibale "sum_profit".

sum_profit += prices[right] - prices[left]

#Proceed indexes.

#left index has to start from right index in next iterate.

#right index proceed each iterate.

left = right

right += 1

#Return "sum_profit".

return sum_profit

2つのポインタとスライディングウインドウを使います。

変数left,rightはポインタです。配列pricesを一巡します。

変数sum_profitは利益の合計を保持しておくためにつかいます。

rightが先に進めて、leftが指す要素よりも大きくなったらその差を利益として加える。

leftをrightまで進める。

rightはループの都度1つ進む。

この動きを繰り返していきます。

③のパターンがあるので、利益が出たらその都度合計に加え、leftをその位置まで進めて再スタートすることを繰り返すイメージです。

解答2：Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        arr=[0 for i in range(len(prices))]
        for i in range(len(prices)-1):
            arr[i+1]=prices[i+1]-prices[i]
        
        maxProfit=0
        for i in range(len(arr)):
            if arr[i]>0:
                maxProfit+=arr[i]
        return maxProfit

class Solution:

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

arr=[0 for i in range(len(prices))]

for i in range(len(prices)-1):

arr[i+1]=prices[i+1]-prices[i]

maxProfit=0

for i in range(len(arr)):

if arr[i]>0:

maxProfit+=arr[i]

return maxProfit

配列pricesと同じ長さの配列arrを作り、各要素には前日の株価との差を入れる。

1日目は保有している株はないので0、2日以降より前日との株価の差が保存される。

配列arrの中で0よりも大きい値を全て合計して返すことで解答とするコード。

最初に配列を作って、値を順番に更新していくのでDPに近いような印象も受ける。

でも、配列を用意するので、空間計算量はO(n)必要。

解答1と異なるのは、毎日購入と売却をすること。

解答1では購入日の株価＜売却日の株価となった場合だけ株を売却して、合計に加えていたけど、こちらの解答では毎日購入と売却を行い、利益が出た日だけを合計する。

ところで、毎日売買を繰り返していくと、最大の利益を計算することはできるものの、損失が発生する日もあるわけで、損失を出さずに利益だけを計算する。みたいなことを現実では考えていかないといけないのかもしれない。

解答3：Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        for i in range(len(prices)-1):
            if prices[i+1] - prices[i] > 0:
                profit += prices[i+1] - prices[i]

        return profit

class Solution:

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

profit = 0

for i in range(len(prices)-1):

if prices[i+1] - prices[i] > 0:

profit += prices[i+1] - prices[i]

return profit

こちらは解答2を改変したコード、

解答2の1つ目のループで、i+1日目の株価がi日目の株価よりも大きければ、その時点で合計に加える。

これなら配列を用意しないので空間計算量はO(1)にできる。

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

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

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：1791. Find Center of Star Graph

次：

LeetCode 解答・解説記事一覧