ゼロから始めるLeetCode Day19 「121. Best Time to Buy and Sell Stock」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day18 「53. Maximum Subarray」
次回
ゼロから始めるLeetCode Day20 「134. Gas Station」

問題

121. Best Time to Buy and Sell Stock

競プロをやったことある人はきっと似たような問題を見たことがあると思います。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
特にこの本とかで。

各日付の株価を格納した配列が与えられます。一回のみ取引が認められるので、その中で最大利益を得るようなアルゴリズムを設計しなさい、という問題です。なお、買う前に売ることはできません。

Input: [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.
Not 7-1 = 6, as selling price needs to be larger than buying price.

株価が1の時に買い、6の時に売ると最大利益を得られます。
そしてその時の利益である5を返しています。

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

この場合は利益を得られる組み合わせが存在しないので0を返します。

解法

わかりやすいものとしては、与えられた配列を前から舐めていき、最小値と最大値比較し、更新していくというやり方があるかなぁと問題をみた時に思いました。

何はともあれ試してみましょう。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        mx, mn = 0, prices and prices[0]
        for i in range(1,len(prices)):
            if prices[i] > prices[i-1]:
                mx = max(mx,prices[i]-mn)
            else:
                mn = min(mn,prices[i])
        return mx
# Runtime: 68 ms, faster than 43.79% of Python3 online submissions for Best Time to Buy and Sell Stock.
# Memory Usage: 15.2 MB, less than 5.75% of Python3 online submissions for Best Time to Buy and Sell Stock.

解ければ良いという考え方っぽくてあまり良い回答とは思えませんね・・・

何か良さげな回答はないかと思ってdiscussを見ていたらやたらfloat(inf)
を使って回答している物が多いのでなんだろうと思って調べてみると、無限大を表すinfというオブジェクトなんですね。

組み込み関数

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        mx, mn = 0, float('inf')
        for price in prices:
            mn = min(mn, price)
            pro = price - mn
            mx = max(mx, pro)
        return mx
# Runtime: 72 ms, faster than 26.68% of Python3 online submissions for Best Time to Buy and Sell Stock.
# Memory Usage: 15.1 MB, less than 5.75% of Python3 online submissions for Best Time to Buy and Sell Stock.

float(inf)を使って書き直してみるとこんな感じ。
知らないことが多いぶん、discussを見るのは勉強になりますね。

良さそうな回答があれば追記します。