买卖股票的最佳时机-LeetCode

121. 买卖股票的最佳时机

🎯 问题描述（来源于LeetCode）

描述：
给定一个数组 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：

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

💻 解题思路

思路1：贪心算法（一次遍历）

思路1：代码实现

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        fare = 0
        # 初始化最低价格为一个较大的值（根据题目约束，最大价格为 10^4）
        min_p = 10**4
        
        for num in prices:
            # 更新历史最低价格
            min_p = min(min_p, num)
            
            # 如果当前价格高于历史最低价格，计算利润并更新最大利润
            if num > min_p:
                fare = max(fare, num - min_p)
                
        return fare

思路1：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是数组 prices 的长度。
  • 我们只遍历数组一次，每次操作都是常数时间。
  • 总时间复杂度为 $O(N)$。
• 空间复杂度：$O(1)$
  • 只使用了常数个额外变量（fare 和 min_p）。

思考

1. 贪心策略：

   • 我们想要获得最大利润，就需要在最低点买入，在最高点卖出。
   • 但是，我们必须在买入之后卖出。
   • 因此，我们维护一个“历史最低价格” min_p，表示到目前为止的最低买入价格。
   • 对于每一天，我们计算如果今天卖出（价格为 num）能获得的利润 num - min_p，并更新最大利润 fare。

2. 变量初始化：

   • fare = 0：初始化最大利润为 0，表示如果不进行任何交易，利润为 0。
   • min_p = 10**4：初始化最低价格为一个较大的值。根据题目约束，股票价格最大为 $10^4$，所以这个初始值能保证第一次比较时 min_p 会被更新为第一个价格。
   • 优化：也可以将 min_p 初始化为 float('inf')，这样更加通用。

3. 逻辑流程：

   • 遍历每一天的价格 num。
   • 首先更新 min_p，确保它始终是到目前为止的最低价格。
   • 然后检查当前价格 num 是否大于 min_p。如果是，说明今天卖出可以获得正利润，我们计算这个利润并更新 fare。
   • 如果 num <= min_p，说明今天的价格比历史最低价格还低（或相等），我们不会在今天卖出，但会更新 min_p。

4. 边界情况：

   • 数组长度为 1：min_p 被更新为唯一的价格，num > min_p 不成立，返回 0。
   • 价格单调递减：min_p 不断更新，num > min_p 始终不成立，返回 0。
   • 价格单调递增：min_p 保持为第一个价格，fare 不断更新为最大利润。