💹
LeetCode: 121. Best Time to Buy and Sell Stock をGoで解く

2024/09/24に公開
LeetCodeの問題を解いたら、記録することにした。Goで解く。

 問題121. Best Time to Buy and Sell Stock
日々の株価が入ったpricesという配列が与えられる。売買をそれぞれ別日に行って、利益が一番高くなったときに、いくら利益がでたかを返すというもの。
例えば、prices = [7,1,5,3,6,4]なら、解は5(2日目に買って、5日目に売ったケース)
難易度はeasyにカテゴライズされる。

 制約1 <= prices.length <= 105

0 <= prices[i] <= 104
売買が同じ日に発生することはない。

 解いてみる
 ぱっと思いついた解き方ぱっと思いついたのは、2重ループで全部確認する方法。時間計算量がO(n^2)であり、pricesの長さ的に多分いくつかテストケース失敗するだろうなと思いつつも、一応試してみた。
solution.go
func maxProfit(prices []int) int {
	profits := make([]int, 0, len(prices))
	for i := 0; i < len(prices); i++ {
		boughtPrice := prices[i]
		var maxProfit int
		for j := i + 1; j < len(prices); j++ {
			soldPrice := prices[j]
			if boughtPrice >= soldPrice {
				continue
			}

			if soldPrice-boughtPrice > maxProfit {
				maxProfit = soldPrice - boughtPrice
			}
		}
		profits = append(profits, maxProfit)
	}
	return slices.Max(profits)
}
これを実行するといくつかテストケースで、Time Limit Exceededになり失敗した。

とりあえず2重ループをやめたい。

 貪欲法で解くこの問題は要は利ざやを大きくすることが目的。そして、もし毎日株のトレードをするならどうするかを考え、「もし今日が最安値の日なら今日買う」「今日売ったら利益が一番高くなりそうだったら売る」を毎日判断する貪欲法で解くことにした。
solution.go
func maxProfit(prices []int) int {
	boughtPrice := prices[0] // 初日に買ったと仮定するところからスタート
	maxProfit := 0

	for i := 1; i < len(prices); i++ {
		todayPrice := prices[i]

		// NOTE: 売買が同じ日に発生することはない
		if boughtPrice > todayPrice {
			// 今日買えばよりお得になるなら今日買う
			boughtPrice = todayPrice
		} else if todayPrice-boughtPrice > maxProfit {
			// 今日売れば利益が最大になるなら、売って、得た利益を暫定最大利益とする
			maxProfit = todayPrice - boughtPrice
		}
	}
	return maxProfit
}
これを実行すると、ちゃんとPassした。
Runtime 104ms (Beats 30.89%)
Memory 8.42mb (Beats 46.23%)
あんまいい成績じゃないな。。
また、pricesのサイズに依存したメモリ確保はしていないのと、pricesの一重ループをしているだけなので、
Time Complexity O(N)
Space Complexity O(1)

となった。

 参考https://algo-method.com/descriptions/95
問題

制約

解いてみる

ぱっと思いついた解き方

貪欲法で解く

参考

Discussion
