LeetCode 题目 121：买卖股票的最佳时机

❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容，和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣！

推荐：数据分析螺丝钉的首页格物致知终身学习期待您的关注

导航：

LeetCode解锁1000题: 打怪升级之旅：每题都包括3-5种算法，以及详细的代码实现，刷题面试跳槽必备
漫画版算法详解：通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读，看一遍就掌握
python源码解读：解读python的源代码与调用关系，快速提升代码质量
python数据分析可视化：企业实战案例：企业级数据分析案例与可视化，提升数据分析思维和可视化能力
程序员必备的数学知识与应用：全面详细的介绍了工程师都必备的数学知识

期待与您一起探索技术、持续学习、一步步打怪升级欢迎订阅本专栏❤️❤️

题目描述

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

在这里插入图片描述

方法一：一次遍历

解题步骤：

初始化两个变量：min_price 为正无穷大，用于记录遍历过程中遇到的最低价格；max_profit 为0，用于记录最大利润。
遍历价格数组，对于每个价格，更新 min_price，并计算以当前价格卖出的利润，更新 max_profit。

Python 代码示例

def maxProfit(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

方法一通过一次遍历来解决买卖股票的最佳时机问题，下面用 ASCII 图形来详细解释这个方法的工作原理。

一次遍历的图解

考虑一个具体的价格数组示例：

prices = [7, 1, 5, 3, 6, 4]

我们需要找到买入和卖出的最佳时机，以获取最大利润。下面的图解将展示如何在一次遍历中实现这一点。

初始状态

初始化 min_price 为正无穷大。
初始化 max_profit 为0。

遍历过程

初始: min_price = inf, max_profit = 0

第1天: price = 7
  min_price = min(inf, 7) = 7
  max_profit = max(0, 7 - 7) = 0
  状态: min_price = 7, max_profit = 0

第2天: price = 1
  min_price = min(7, 1) = 1
  max_profit = max(0, 1 - 1) = 0
  状态: min_price = 1, max_profit = 0

第3天: price = 5
  min_price = min(1, 5) = 1
  max_profit = max(0, 5 - 1) = 4
  状态: min_price = 1, max_profit = 4

第4天: price = 3
  min_price = min(1, 3) = 1
  max_profit = max(4, 3 - 1) = 4
  状态: min_price = 1, max_profit = 4

第5天: price = 6
  min_price = min(1, 6) = 1
  max_profit = max(4, 6 - 1) = 5
  状态: min_price = 1, max_profit = 5

第6天: price = 4
  min_price = min(1, 4) = 1
  max_profit = max(5, 4 - 1) = 5
  状态: min_price = 1, max_profit = 5

结果

最终得到的最大利润是 5，即在价格为 1 的第2天买入，在价格为 6 的第5天卖出。

总结步骤

初始化两个变量 min_price 和 max_profit。
遍历价格数组，更新 min_price 为遇到的最小价格。
对每个价格，计算如果当天卖出的利润，并更新 max_profit。
最后的 max_profit 就是最大利润。

这种方法简单而有效，只需一次遍历就能找到最大利润，同时也避免了复杂的计算和额外的空间开销。

方法二：动态规划

解题步骤：

使用一个数组 dp 来记录每天结束时可能得到的最大利润。
第一天的利润为0；从第二天开始，更新当前最小购买价格，并计算当前可能的最大利润。

Python 代码示例

def maxProfit(prices):
    if not prices:
        return 0
    n = len(prices)
    min_price = prices[0]
    max_profit = 0
    for i in range(1, n):
        min_price = min(min_price, prices[i])
        max_profit = max(max_profit, prices[i] - min_price)
    return max_profit

方法三：分治法

解题步骤：

将价格数组分为两部分，递归地找出左右两部分的最大利润。
计算跨越两部分的最大利润，即左侧的最低价格和右侧的最高价格之差。
最大利润是左侧、右侧和跨中三者的最大值。

Python 代码示例

def maxProfit(prices):
    def maxCrossingProfit(left, right):
        if left == right:
            return 0
        mid = (left + right) // 2
        min_left = min(prices[left:mid+1])
        max_right = max(prices[mid+1:right+1])
        return max(0, max_right - min_left)
    
    def divideAndConquer(left, right):
        if left >= right:
            return 0
        mid = (left + right) // 2
        left_profit = divideAndConquer(left, mid)
        right_profit = divideAndConquer(mid + 1, right)
        cross_profit = maxCrossingProfit(left, right)
        return max(left_profit, right_profit, cross_profit)
    
    return divideAndConquer(0, len(prices) - 1)

方法四：前缀最小值与后缀最大值

解题步骤：

创建两个数组，分别存储从左到右的前缀最小值和从右到左的后缀最大值。
遍历 prices 数组，计算利用前缀最小和后缀最大计算可能的最大利润。

Python 代码示例

def maxProfit(prices):
    n = len(prices)
    if n == 0:
        return 0
    min_prefix = [0] * n
    max_suffix = [0] * n
    min_prefix[0] = prices[0]
    for i in range(1, n):
        min_prefix[i] = min(min_prefix[i-1], prices[i])
    max_suffix[n-1] = prices[n-1]
    for i in range(n-2, -1, -1):
        max_suffix[i] = max(max_suffix[i+1], prices[i])
    max_profit = 0
    for i in range(n):
        max_profit = max(max_profit, max_suffix[i] - min_prefix[i])
    return max_profit

方法五：Kadane算法变形

解题步骤：

理解为找最大子数组和的问题，其中“价格差”数组是原数组相邻元素的差值。
使用Kadane算法找到最大子数组和，即为最大利润。

Python 代码示例

def maxProfit(prices):
    max_current = max_global = 0
    for i in range(1, len(prices)):
        max_current = max(0, max_current + prices[i] - prices[i-1])
        if max_current > max_global:
            max_global = max_current
    return max_global