type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一个数组
prices，它的第i个元素prices[i] 表示一支给定股票第i天的价格。只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回可以从这笔交易中获取的最大利润。如果不能获取任何利润，返回
0 。示例 1：
示例 2：
解法一：暴力枚举
我可以在任何一天买入，然后在之后的任意一天卖出，那就两层循环试试所有可能的组合：
- 外层循环选买入那天；
- 内层循环选卖出那天；
- 对每一对
(i, j)（j > i）都算一算利润prices[j] - prices[i]；
- 保留最大利润。
问题是如果有一万个价格，那要比的组合数量就是 n² 级别。
复杂度
- 时间：O(n²)，两层循环。通常会超时。
- 空间：O(1)，只用了常数个变量。
解法二：贪心（推荐）
我们每天都想两件事：
- 到目前为止，哪天的价格最低？
这天是我理想的买入点；
这里是“历史最低价”，是指“到今天为止能作为买入点的最低价”，不是全局最低价。
- 如果我今天卖出，能赚多少钱？
profit_today = price[i] - min_price然后我们就不断更新：
min_price：迄今为止的最低价；
max_profit：迄今为止的最大利润。
也就是，每一天都假设自己今天卖出，看能不能赚得更多。
复杂度
- 时间：O(n)，只遍历一次；
- 空间：O(1)。
解法三：一维动态规划
解法二的“贪心”思路可以理解为“动态规划”的一种简化形式。
dp[i] 表示：到第 i 天为止的最大利润。有两种可能：
- 今天不卖，那利润就是昨天的
dp[i-1]；
- 今天卖了，那利润就是
prices[i] - min_price_before_i。
所以递推公式是：
在每一步同时更新
min_price。复杂度
- 时间：O(n)
- 空间：O(n) （因为有 dp 数组）
dp 数组没必要保留，因为每一步只依赖前一天, 可以压缩成两个变量，就变回了解法二的“贪心法”。
解法四：状态机动态规划（通用解法）
在更复杂的股票题（比如允许多次交易、含冷冻期等）中，我们常用“状态机”来描述买卖过程。
这道题只能买卖一次，也能写出“最通用”的 DP 模型。（这个模型可以扩展到后续股票题，122、123、309、714）。
设：
dp0: 从未买过（始终不买）
dp1: 买入一次，尚未卖出
dp2: 买入一次并卖出一次
初始状态：
状态转移：
dp0 = 0（始终不买）
dp1 = max(dp1, dp0 - prices[i])（不买 or 今天买）
dp2 = max(dp2, dp1 + prices[i])（不卖 or 今天卖）
最后答案是
max(dp0, dp2)，因为卖出后手里没股票，利润才是最终收益。复杂度
- 时间：O(n)
- 空间：O(1)
解法五：双指针（滑动窗口）
这个方法其实和解法二的一次遍历的逻辑一样，只是换了一种思维方式：
我们用两个指针
l（买入点）和 r（卖出点）在数组上滑动。- 右指针负责“向后探索更高的卖出价”，
- 左指针负责“锁定当前最低的买入价”。
步骤：
初始化：
l = 0, r = 1如果
prices[l] < prices[r]，说明可以赚钱，计算利润；如果
prices[l] >= prices[r]，说明左边价格更高，不划算，于是更新左指针 l = r；每次都更新
max_profit。这样右指针一路往右扫，左指针始终保持在“当前最低买入点”。
复杂度
- 时间：O(n)
- 空间：O(1)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-121-买卖股票的最佳时机
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 116] 填充每个节点的下一个右侧节点指针
下一篇
[Leetcode 122] 买卖股票的最好时间 II