LeetCode 121. Best Time to Buy and Sell Stock

はじめに

LeetCode 「121. Best Time to Buy and Sell Stock」の問題をGoで解きました。

問題

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

問題文

You are given an array prices where prices[i] is the price of a given stock on the ith 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.

和訳
配列 prices が与えられます。ここで、prices[i] は i 日目の特定の株式の価格です。1 日を選択して 1 つの株式を購入し、将来の別の日にその株式を売却することで、利益を最大化したいと考えています。このトランザクションから達成できる最大の利益を返します。利益を達成できない場合は、0 を返します。

例

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.

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

制約

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

解答

株の売却の利益を最大化する問題です。
prices を左から順に見ていき、以下の2つのポイントを管理します

• minPrice: これまでの最小価格（最も安く買える価格）
• profit: 現時点での最大利益

これを1回のループで更新しながら解を求めます。

例1だと、利益が最大となる購入・売却の位置は以下となります。

  [7,  1,  5,  3,  6,  4]
       ↑           ↑
      購入         売却

まず、7と1で見たときに、数の小さい1が仮の購入価格になります。
そこから、購入価格が最小となるものを更新していき、利益の最大値も更新していくと答えが出ます。

コード

func maxProfit(prices []int) int {
    minPrice := prices[0]
    profit := 0

    for i := 1; i < len(prices); i++ {
        if prices[i] < minPrice {
            minPrice = prices[i] // 買い時を更新
        } else {
            profit = max(profit, prices[i] - minPrice) // 利益の最大値を更新
        }
    }

    return profit
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

計算量

• 時間的計算量：O(n)
• 空間的計算量：O(1)