LeetCode - 121. Best Time to Buy and Sell Stock

題目: 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%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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 bestProfit

C#:

Runtime 238 ms(84.31%), Memory 49.5 MB(29.32%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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%)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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)

1
2
3
4
5
6
7
8
9


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;
}