【121. 买卖股票的最佳时机】——贪心算法/动态规划

121. 买卖股票的最佳时机

一、题目难度

简单

三、题目描述

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

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

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

四、示例

示例1

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

示例2

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

五、提示

1 <= prices.length <= 105
0 <= prices[i] <= 104

六、贪心算法求解思路

（一）整体思路

我们的目标是通过一次买入和一次卖出操作来获取最大利润。贪心算法的思路就是在遍历股票价格数组的过程中，始终记录当前已经出现过的最低买入价格，然后用当前价格减去这个最低买入价格，得到当前可能的最大利润，不断更新这个最大利润值，直到遍历完整个数组。

（二）贪心思路

贪心算法一般步骤的分析：

1. 将问题分解为若干个子问题

分析：
在本题中，可以将整个股票交易过程按每一天来看作一个子问题。每一天我们都面临一个决策：是否更新最低买入价格以及基于当前价格和最低买入价格计算可能的最大利润。通过依次处理每一天的情况，最终汇总得到整个交易周期内的最大利润，所以整个问题可以分解为按天来考虑的一系列子问题。
初始化变量：
- 设 min_price 为一个较大的值（可以初始化为 prices[0]，因为后续会不断更新它为更小的值），它用来记录到目前为止出现过的最低买入价格。
- 设 max_profit 为 0，它用来记录到目前为止能获取到的最大利润。

2. 找出适合的贪心策略

分析：
贪心策略就是在遍历股票价格数组的过程中，始终保持记录到当前为止所出现过的最低买入价格。因为我们希望买入价格尽可能低，这样在后续任何一天卖出时，才有可能获得最大的利润。所以，每到一天，就比较当天的股票价格和已记录的最低买入价格，如果当天价格更低，就更新最低买入价格，这就是我们确定的贪心策略。

3. 求解每一个子问题的最优解

分析：
对于每一天这个子问题，其最优解就是基于当前已经确定的最低买入价格（通过前面的贪心策略不断更新得到），计算当天卖出能获得的最大利润。即通过当天的股票价格减去最低买入价格得到一个差值，如果这个差值大于之前记录的最大利润，就更新最大利润值。
遍历数组：
- 从数组的第二个元素（索引为 1）开始遍历 prices 数组，因为第一个元素已经作为初始的 min_price 考虑过了。
- 对于每个元素 prices[i]：
  - 首先更新 min_price：比较当前元素 prices[i] 和 min_price，如果 prices[i] 小于 min_price，则将 min_price 更新为 prices[i]。这一步是为了始终记录到目前为止出现过的最低买入价格。
  - 然后更新 max_profit：计算当前价格 prices[i] 减去 min_price 的差值，得到当前可能的最大利润，将这个差值与 max_profit 进行比较，如果差值大于 max_profit，则将 max_profit 更新为这个差值。这一步是为了不断更新能获取到的最大利润值。

4. 将局部最优解堆叠成全局最优解

分析：
在遍历完整个数组后，最后记录下来的最大利润值就是全局最优解。因为在每一天我们都通过贪心策略找到了当天基于最低买入价格能获得的最大利润（局部最优解），随着遍历的进行，不断更新这个最大利润值，最终这个值就代表了在整个交易周期内能够获得的最大利润，也就是将每一天的局部最优解堆叠起来形成了全局最优解。
返回结果：
- 遍历完整个数组后，max_profit 中存储的就是通过一次买入和一次卖出操作所能获取到的最大利润，直接返回 max_profit 即可。

代码对应解释

def maxProfit(prices):
    if not prices:
        return 0

    min_price = prices[0]  # 初始化最低买入价格为第一天的价格
    max_profit = 0  # 初始化最大利润为0

    # 以下循环对应处理每一天的子问题
    for price in prices[1:]:
        # 对应找出适合的贪心策略步骤，更新最低买入价格
        if price < min_price:
            min_price = price

        profit = price - min_price  # 计算当天基于当前最低买入价格的利润

        # 对应求解每一个子问题的最优解步骤，更新最大利润
        if profit > max_profit:
            max_profit = profit

    return max_profit

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 特殊情况：空集
        if not prices:
            return 0
        
        # 正常情况，初始化
        min_price = prices[0]  # 初始化当前最低买入价格为prices[0]
        max_profit = 0         # 初始化最大利润为0    
        # 从索引1（实际2）开始循环遍历股票数组，直接遍历price值
        # 循环处理每一天的子问题
        for price in prices[1:]:
            # 更新当前
            min_price = min(price, min_price)
            cur_profit = price - min_price
            max_profit = max(max_profit, cur_profit)
        return max_profit

在上述代码中：

首先判断输入的数组是否为空，如果为空则返回 0。
接着初始化 min_price 和 max_profit。
然后通过循环遍历数组，在循环中不断更新 min_price 和 max_profit。
最后返回 max_profit，它就是所能获取到的最大利润。

动态规划解法

思路：通过定义状态与状态转移方程解决问题
- dp[i]定义为第i天卖出股票所能获得的利润
- dp[i] = max(dp[i - 1], prices[i] - min_price)是状态方程
- 其中，min_price是第i天之前（包括第i天）的最低股票购入价格
代码步骤：
- 特解：空集
- 初始化：
  - 收入数组dp：一维dp[i]，长len(prices)，所有值为0
  - 最低买入价格min_price = prices[0]
- 循环遍历数组:(从第二天索引1开始)
  - 首先更新最低买入价格
  - dp[i] = max(dp[i - 1], prices[i] - min_price
  - 返回最后一个dp[-1]
复杂度分析：
- 时间复杂度：一次循环遍历，每次循环执行的都是比较和赋值，故 $O (n)$ 。
- 空间复杂度：用到长度n的数组dp存储中间状态，故 $O (n)$ 。

def maxProfit(prices):
    if not prices:
        return 0

    n = len(prices)
    dp = [0] * n
    min_price = prices[0]

    for i in range(1, n):
        if prices[i] < min_price:
            min_price = prices[i]

        dp[i] = max(dp[i - 1], prices[i] - min_price)

    return dp[-1]