LeetCodeに毎日挑戦してみた 121 Best Time to Buy and Sell Stock(Python、Go)


Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門+アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

30問目(問題121)

121 Best Time to Buy and Sell Stock

問題内容

Say you have an array for which the i*th element is the price of a given stock on day *i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

日本語訳

i番目の要素がi日目の特定の株式の価格である配列があるとします。

最大で1つのトランザクションのみを完了することが許可されている場合(つまり、1つを購入し、1株の株式を売却する)、最大の利益を見つけるためのアルゴリズムを設計します。

購入する前に株式を売却することはできませんのでご注意ください。

Example 1:

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.

Example 2:

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

考え方

  1. 配列を全て探索するために最大利益と最小値を保存する変数を初期化します

  2. ループで回して小さい方を返すminと大きい方を返すmaxを使います

  3. 戻り値には最大利益であるmax_profitを返します

解答コード

def maxProfit(prices):
    max_profit, min_price = 0, float('inf')
    for price in prices:
        min_price = min(min_price, price)
        profit = price - min_price
        max_profit = max(max_profit, profit)
    return max_profit
  • Goでも書いてみます!
func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    max, lowest := 0, 0
    for i := 1; i < len(prices); i++ {
        if prices[i] < prices[lowest] {
            lowest = i
        } else if cur := prices[i] - prices[lowest]; cur > max {
            max = cur
        }
    }
    return max
}