【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：

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

提示：

• 1 <= prices.length <=
• 0 <= prices[i] <=

解题思路

核心逻辑是记录历史最低买入价，实时计算当日卖出的利润：

1. 初始化 “最低买入价” 为第一天价格，“最大利润” 为 0；
2. 遍历后续每天的价格：
   • 若当日价格低于 “最低买入价”，更新 “最低买入价”；
   • 计算 “当日价格 - 最低买入价” 的利润，若大于当前 “最大利润”，则更新 “最大利润”；
3. 遍历结束后，返回 “最大利润”（若利润为负则返回 0）。

示例验证

示例 1：输入prices = [7,1,5,3,6,4]

• 遍历过程：
  • 价格 1：min_price=1，利润 0 → max_profit=0；
  • 价格 5：利润 5-1=4 → max_profit=4；
  • 价格 3：利润 3-1=2 → 不更新；
  • 价格 6：利润 6-1=5 → max_profit=5；
  • 价格 4：利润 4-1=3 → 不更新；
• 最终返回：5（符合预期）。

示例 2：输入prices = [7,6,4,3,1]

• 遍历过程中，每日利润均为负数，max_profit 始终保持 0；
• 最终返回：0（符合预期）。

核心优势

• 时间复杂度 O (n)：仅一次线性遍历，无嵌套操作，适配 10⁵级别的数组长度；
• 空间复杂度 O (1)：仅使用 2 个变量存储中间结果，无额外空间开销；
• 鲁棒性：处理了 “数组长度不足 2”“价格持续下跌” 等边界场景。

Python代码：

from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) < 2: return 0 min_price = prices[0] max_profit = 0 for price in prices[1:]: min_price = min(min_price, price) current_profit = price - min_price max_profit = max(max_profit, current_profit) return max_profit # 测试用例 if __name__ == "__main__": solution = Solution() # 示例1 print(f"示例1输入: [7,1,5,3,6,4]") print(f"示例1输出: {solution.maxProfit([7,1,5,3,6,4])}") # 示例2 print(f"示例2输入: [7,6,4,3,1]") print(f"示例2输出: {solution.maxProfit([7,6,4,3,1])}") # 边界用例：数组长度为1 print(f"示例3输入: [5]") print(f"示例3输出: {solution.maxProfit([5])}") # 边界用例：价格持续上涨 print(f"示例4输入: [1,2,3,4,5]") print(f"示例4输出: {solution.maxProfit([1,2,3,4,5])}")

LeetCode提交代码：

from typing import List class Solution: def maxProfit(self, prices: List[int]) -> int: # 边界条件：数组长度不足2时，无法完成交易，利润为0 if len(prices) < 2: return 0 min_price = prices[0] # 记录历史最低买入价 max_profit = 0 # 记录最大利润 # 遍历每天的价格，计算最大利润 for price in prices[1:]: # 更新历史最低买入价 min_price = min(min_price, price) # 计算当日卖出的利润，并更新最大利润 current_profit = price - min_price max_profit = max(max_profit, current_profit) return max_profit

程序运行结果如下：

示例1输入: [7,1,5,3,6,4] 示例1输出: 5 示例2输入: [7,6,4,3,1] 示例2输出: 0 示例3输入: [5] 示例3输出: 0 示例4输入: [1,2,3,4,5] 示例4输出: 4

总结

本文介绍了股票买卖问题的解决方案，要求在给定股票价格数组中找到最大利润。算法通过记录历史最低买入价并实时计算当前利润来实现，时间复杂度O(n)，空间复杂度O(1)。关键步骤包括：初始化最低价为第一天价格，遍历后续价格更新最低价并计算利润，最终返回最大利润（若为负则返回0）。示例验证和边界条件处理证明了算法的正确性和鲁棒性，适用于不同价格趋势的输入。Python代码实现简洁高效，通过测试用例验证了算法的有效性。