121. 买卖股票的最佳时机 (Easy)
专题归类： 11-贪心 LeetCode 链接： https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票，设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：5
解释：在第 2 天（价格 = 1）的时候买入，在第 5 天（价格 = 6）的时候卖出，最大利润 = 6 - 1 = 5。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下，没有交易完成，所以最大利润为 0。
题目详细分析
数据范围： 1 <= prices.length <= 10^5，0 <= prices[i] <= 10^4
核心约束：
- 只能买卖一次（一次买入一次卖出），且必须先买后卖
- 买入必须在卖出之前（即卖出的下标 > 买入的下标）
- 若价格一直下跌，最大利润为 0（不交易）
关键洞察：
- 这是一个单次交易问题，相当于在历史最低点买入，未来最高点卖出
O(n)遍历即可，无需使用O(n^2)的暴力法- 因为只能交易一次，局部最优（每天记录历史最低价）就是全局最优，这是贪心能用的根本原因
小白版直白理解
就像你逛街想买一件东西，你知道它未来几天的价格。你只能买一次、卖一次。那你肯定会想：在价格最低的那天买入，然后在之后价格最高的那天卖出。但如果价格一直跌，那就不买，利润为 0。
换种说法：你每天记录下”到今天为止的最低价格”，然后每天问自己：“如果我今天卖出，能赚多少钱？” 把每天算出的最大利润记下来，取最大的那个就是答案。
解题思路
思路一：贪心 / 一次遍历（推荐）
思路讲解： 核心思想是在遍历过程中维护两个变量：
min_price：遍历到当前位置时的最低价格（历史最低价）max_profit：到当前位置时能获得的最大利润
每遍历一天，先用当天价格更新 min_price（保证买入价最低），再计算”如果今天卖出”的利润 price - min_price，用它更新 max_profit。这就是贪心思想的体现——在每一天都做局部最优决策（找历史最低买入价），最终得到全局最优（最大利润）。
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时间复杂度： O(n) | 空间复杂度： O(1)
思路二：动态规划
思路讲解： 用两个状态表示第 i 天的最大收益：
dp0：第 i 天不持有股票时的最大现金（即已卖出或不买入）dp1：第 i 天持有股票时的最大现金（即已买入）
初始化：dp0 = 0（没买），dp1 = -prices[0]（第一天买入花掉 prices[0]）
转移：dp0 = max(dp0, dp1 + price)（今天卖出或不卖），dp1 = max(dp1, -price)（今天买入或不买，注意只能买一次所以是 -price）
def maxProfit(prices):
dp0 = 0 # 不持有股票的最大现金
dp1 = -prices[0] # 持有股票的最大现金（负值表示成本）
for price in prices[1:]:
dp0 = max(dp0, dp1 + price) # 卖出 or 不动
dp1 = max(dp1, -price) # 买入 or 不动（只能买一次）
return dp0时间复杂度： O(n) | 空间复杂度： O(1)
易错点
- 数组长度为 1：只能买入无法卖出，利润为 0，代码应能正确处理
- 价格一直下跌：不交易利润为 0，不要返回负数
- 先买后卖顺序：不能先卖后买（不能做空），利润 = 后面价格 - 前面价格必须非负才能交易
- 初始值设置：
min_price初始化为float('inf')而非prices[0]，这样第一个元素就能正确更新 - DP 写法中 dp1 的更新：只能用
-price而非dp1（因为只能买一次），如果允许多次买卖则用dp0 - price
框架提炼
贪心模板：维护历史最值
def solve(prices):
best_buy = INF # 维护历史最优买入条件
best_profit = 0 # 维护历史最优结果
for x in prices:
best_buy = min(best_buy, x) # 更新"买入"条件
best_profit = max(best_profit, x - best_buy) # 更新结果
return best_profit这类”一次交易”问题都可以套用此模板——维护一个历史最值，然后在遍历中持续更新答案。
DP 框架（状态机）：
dp0, dp1 = 0, -inf
for price in prices:
dp0 = max(dp0, dp1 + price) # 不持股：之前就不持股 / 今天卖出
dp1 = max(dp1, -price) # 持股：之前就持股 / 今天买入这个 DP 框架可以推广到”可以交易 k 次”的通用股票问题。
关联题目
- 122-买卖股票的最佳时机II — 可以无限次买卖，DP 转移改为
dp1 = max(dp1, dp0 - price) - 123-买卖股票的最佳时机III — 最多两笔交易，DP 升维为
dp[i][k][0/1] - 188-买卖股票的最佳时机IV — 最多 k 笔交易，通用状态机 DP
- 309-最佳买卖股票时机含冷冻期 — 卖出后有一天的冷冻期
- 714-买卖股票的最佳时机含手续费 — 每次交易需要支付手续费