LeeCode 每日一题121:股票卖出的最佳时机

开了一个新坑, 今天附带了一个改一条语句提升10倍性能的彩蛋.

题目

动手试试再看解决方法吧

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入
     在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

暴力解决

首先来看看暴力解决这道题的算法,以类似冒泡算法的方式,两层遍历整个数组确定最大利润, 这种方式最蠢, 最容易想到. 在 LeeCode 中, C语言凭借更好的性能还能通过, 而Python就直接超时了.

结果

(想不到这种解法还能超过25%的提交, 看来不够暴力)

C语言实现:

int maxProfit(int* prices, int pricesSize) {
    int i, j;
    int maxProfit = 0;
    
    for(i = 0; i<pricesSize-1; i++){
        for(j=i+1; j<pricesSize; j++){
            if(prices[i]<prices[j] && prices[j]-prices[i]>maxProfit){
                maxProfit = prices[j]-prices[i];
            }
        }
    }
    
    return maxProfit;
}

Python实现

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_profit = 0
        for i in range(len(prices)-1):
            for j in range(i+1, len(prices)):
                if(prices[j]-prices[i] > max_profit):
                    max_profit = prices[j]-prices[i]
        return max_profit

动态规划

查找整个数组的最大利润
转化为查找到当前位置的最大利润
而到当前的最大利润又可以转化为此前最大利润与当前卖出和最小买入股票之差.

有点绕?转化为伪代码试试:

前i天的最大收益 = max{前i-1天的最大收益，第i天的卖出价格-前i-1天最小买入价格}

C实现

int maxProfit(int* prices, int pricesSize) {
    if(pricesSize < 0)
        return 0;
    
    int i, j;
    int maxProfit = 0;
    int minPrice = prices[0];
    
    for(i = 0; i<pricesSize; i++){
        minPrice = (minPrice>prices[i])?prices[i]:minPrice;
        maxProfit = (maxProfit>prices[i]-minPrice)?maxProfit:prices[i]-minPrice;
    }
    
    return maxProfit;
}

结果
看到居然才超过43%的用户,我又再检查了一遍, 把三目运算改为普通的if else,然后神奇的事情发生了...

改完超过了99.38%的用户! 耗时瞬间从 48 ms 下降至 4 ms, 一个小小语句提升了10倍性能, 可见三目运算耗能之大.

C语言实现改进版

int maxProfit(int* prices, int pricesSize) {
    if(pricesSize < 0)
        return 0;
    
    int i, j;
    int maxProfit = 0;
    int minPrice = prices[0];
    
    for(i = 0; i<pricesSize; i++){
        if (prices[i] - minPrice > maxProfit)
            maxProfit = prices[i] - minPrice;
        if (prices[i] < minPrice)
            minPrice = prices[i];
    }
    
    return maxProfit;
}

结果

Python 实现

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_profit = 0
        if(len(prices)>0): 
            min_price = prices[0]
            for i in range(len(prices)):
                min_price = min(min_price, prices[i])
                max_profit = max(max_profit, prices[i] - min_price)
            return max_profit
        else:
            return max_profit

结果