LeetCode: 122. Best Time to Buy and Sell Stock II をGoで解く

LeetCodeの問題を解いたら、記録することにした。Goで解く。

問題

122. Best Time to Buy and Sell Stock II

日々の株価が入ったpricesという配列が与えられる。同日に売り買いしてもいい、かつ、期間内に複数回売買していい場合、利益は最大でいくら出せるかという問題。

例えば、prices = [7,1,5,3,6,4]なら、解は7(2日目に買って3日目に利確。4日目に買って5日目に利確)

難易度はmediumにカテゴライズされる。

制約

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

売買が同じ日に発生してもいい。期間内に複数回売買してもいい。ただし、株は一個しか同時には持てない。

解いてみる

思いついた解き方

次の日に下がるなら（今日価格が上がりきっているなら）利確する。を繰り返すと最大利益になる。

これを実現すると以下コードとなった。「今日買ったことにしてしまう」とかはずるいかもしれない。

solution.go

func maxProfit(prices []int) int {
	var profit int
	boughtPrice := prices[0]
	for i := 1; i < len(prices); i++ {
		todayPrice := prices[i]
		// 最終日かつ利益が出るなら利確しておしまい
		isFinalDay := i == len(prices)-1
		if isFinalDay {
			if boughtPrice < todayPrice {
				profit += todayPrice - boughtPrice
			}
			break
		}

		// 今日をピークに明日値下がりするなら今日利確して、買い直す
		// you can buy it then immediately sell it on the same day.なのでOK
		tomorrowPrice := prices[i+1]
		if boughtPrice < todayPrice && todayPrice > tomorrowPrice {
			profit += todayPrice - boughtPrice
			boughtPrice = todayPrice
		}

		// 買ったときより今日のほうが安いなら、今日買ったことにしてしまう
		if boughtPrice > todayPrice {
			boughtPrice = todayPrice
		}
	}
	return profit
}

これを実行すると、ちゃんとPassした。

• Runtime 4ms (Beats 64.31%)
• Memory 3.34mb (Beats 73.04%)

また、pricesのサイズに依存したメモリ確保はしていないのと、pricesの一重ループをしているだけなので、

• Time Complexity O(N)
• Space Complexity O(1)