LeetCode / 3 min read
LeetCode - 121. Best Time to Buy and Sell Stock
LeetCode - 121. Best Time to Buy and Sell Stock
On this page
題目: 121. Best Time to Buy and Sell Stock
給一陣列(prices)，陣列中各element代表各天的股價。 你可以在某一天買進，在某一天賣出，求最大利潤。 如果沒有最大利潤，則返回0。
解題思路
找最大、最小值，但最小值的索引值需小於最大值的索引值，因為你不能穿越時空回到過去賣股票。
每次iterate時，以當前股價計算profit，並記錄best profit與最小值。
Code
Java:
Runtime 1 ms(100%), Memory 59 MB(82.59%)
class Solution { public int maxProfit(int[] prices) { int bestProfit = 0; int min = Integer.MAX_VALUE; for (int i = 0; i < prices.length; i++){ int profit = prices[i] - min; if (profit > bestProfit){ bestProfit = profit; } if (prices[i] < min){ min = prices[i]; } } return bestProfit; }}Python3:
Runtime 940 ms(98.55%),Memory 25 MB(86.59%)
class Solution: def maxProfit(self, prices: List[int]) -> int: bestProfit = 0 minPrice = 10001 for i in range(len(prices)): profit = prices[i] - minPrice if profit > bestProfit: bestProfit = profit if prices[i] < minPrice: minPrice = prices[i] return bestProfitC#:
Runtime 238 ms(84.31%), Memory 49.5 MB(29.32%)
public class Solution { public int MaxProfit(int[] prices) { int bestProfit = 0; int min = Int32.MaxValue; for (int i = 0; i < prices.Length; i++){ int profit = prices[i] - min; bestProfit = Math.Max(profit, bestProfit); min = Math.Min(prices[i], min); } return bestProfit; }}Golang:
Runtime 119 ms(90.37%), Memory 8.8 MB(37.19%)
func maxProfit(prices []int) int { bestProfit := 0; min := math.MaxInt32; for i := 0; i < len(prices); i++ { var profit = prices[i] - min; if profit > bestProfit{ bestProfit = profit; } if prices[i] < min { min = prices[i] } } return bestProfit;}C++:
Runtime 131 ms(92.72), Memory 93.3 MB(54.15)
class Solution {public: int maxProfit(vector<int>& prices) { int bestProfit = 0, minPrice = INT_MAX; for (int i=0; i<prices.size(); i++){ int profit = prices[i] - minPrice; minPrice = min(prices[i], minPrice); bestProfit = max(profit, bestProfit); } return bestProfit; }};C:
Runtime 145 ms(82.69%), Memory 13.1 MB(37.69)
int maxProfit(int* prices, int pricesSize){ int bestProfit = 0, minPrice = INT_MAX; for (int i=0; i<pricesSize; i++){ int profit = prices[i] - minPrice; minPrice = prices[i] < minPrice ? prices[i] : minPrice; bestProfit = profit > bestProfit ? profit : bestProfit; } return bestProfit;}