#121
简单
高频
动态规划买卖股票的最佳时机
这是一道围绕数组展开的高频练习。建议先掌握「动态规划」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
题目分析
给你一个数组 prices，prices[i] 表示第 i 天的股价。
你只能买一次、卖一次，而且必须先买后卖。要求你算出最多能赚多少钱；如果怎么做都赚不到钱，就返回 0。
一句话概括：
遍历价格数组，在保证先买后卖的前提下，找到最大利润。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：一边遍历价格，一边维护历史最低买入价和当前能获得的最大利润。
推荐代码
推荐解法：动态规划
时间复杂度： O(n)
空间复杂度： O(1)
核心思路： 一边遍历价格，一边维护历史最低买入价和当前能获得的最大利润。
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
}结构化讲解
面试时怎么讲
开场思路
这题我会一趟扫描完成，核心是维护历史最低买入价。
核心过程
- 遍历每一天的价格。
- 用一个变量记录到当前为止见过的最低价格。
- 把今天作为卖出日，利润就是
price - minPrice。 - 持续更新最大利润，遍历结束后返回答案。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(1)。
面试补一句：这题本质是状态压缩，不必真的建 DP 数组。
核心思路
这题不需要真的枚举买卖日。只要知道“到今天为止最低买入价是多少”，今天卖出能赚多少钱就能立刻算出来。
步骤讲解
1
初始化最低价格和最大利润
遍历前让 minPrice 表示历史最低买入价，maxProfit 表示当前最佳答案。
为什么这样做：后面每一天都只依赖这两个状态，不需要额外数组。
对应代码提示：int minPrice = Integer.MAX_VALUE; int maxProfit = 0;
2
先更新历史最低买入价
如果今天价格更低，就把它记作新的最优买入点。
为什么这样做：未来任何一天卖出，都希望搭配尽量低的买入价。
对应代码提示：minPrice = Math.min(minPrice, price);
3
把今天当卖出日计算利润
用 price - minPrice 计算今天卖出能赚多少。
为什么这样做：题目只允许买一次卖一次，所以利润由当前价格减去历史最低价直接决定。
对应代码提示：maxProfit = Math.max(maxProfit, price - minPrice);
易错点
把最低价更新放在错误位置
如果思路混乱，可能把未来价格当成过去的买入点。
正确理解：
minPrice 必须表示“当前位置之前见过的最低价”。允许卖在买之前
如果最低价来自当前之后的某天，利润就没有意义。
正确理解：坚持单向遍历，所有状态都只来自过去。
没利润时返回负数
题目要求做不到盈利时返回 0。
正确理解：初始答案设为 0，只在更大时更新。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(1)
比其他方案更好在哪里：比枚举所有买卖日组合的
O(n^2) 暴力法高效很多。适用判断：当题目要求“截至当前位置的最优值”时，优先思考能否边遍历边压缩状态。
额外提醒
- 最低价代表最优买入时机，当前价代表尝试卖出时机。
动画演示
如果你还没完全看懂，可以展开动画演示。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
动态规划动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
当前最低价格
-
当前最大利润
0
当前天数
0/6
股票价格走势
7
1
5
3
6
4
买入点: -
卖出点: -
操作日志
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。