121. 买卖股票的最佳时机

解答

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1:
            return 0
        buy = prices[0]
      # 建立一个列表保存每次买卖的差值,比较找到最大值
        max_prices = [0]
        if n == 2:
            if prices[0] < prices[1]:
                return prices[1] - prices[0]
            else:
                return 0
        for i in range(1, n-1):
            # buy
            # 如果后一个值小于前一个值,买入点被更新到后一个值
            if prices[i] < prices[i - 1]:
                buy = prices[i]
            # sell
            for j in range(i, n):
            # 卖出点位置大于买入点,
            # 记录在当前买入点情况下,各个不同卖出点和该买入点的差值
                if prices[j] > prices[j - 1]:
                    profit = prices[j] - buy
                    max_prices.append(profit)
        return max(max_prices)
                    

时间复杂度O(n2)
考虑的特殊情况较多,要考虑到n=1和n=2的特殊情况。

改进后如下:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1:
            return 0
        buy = prices[0]
        max_profit = [0]
        for i in range(1, n):
            # buy
            if prices[i] < buy:
                buy = prices[i]
            else:
                profit = prices[i] - buy
                max_profit.append(profit)
        return max(max_profit)

再节约空间复杂度
取消max_profit的列表形式,而变为实数

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n <= 1:
            return 0
        buy = prices[0]
        max_profit = 0
        for i in range(1, n):
            # buy
            if prices[i] < buy:
                buy = prices[i]
            else:
                profit = prices[i] - buy
                if profit > max_profit:
                    max_profit = profit
        return max_profit
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容