121. 买卖股票的最佳时机
查看题目简单
数组
高频
解法一：动态规划
时间复杂度：O(n) | 空间复杂度：O(1) | 推荐使用
动画演示
当前最低价格
-
当前最大利润
0
当前天数
0/6
股票价格走势
7
1
5
3
6
4
买入点: -
卖出点: -
操作日志
代码实现
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;
}
}时间复杂度：O(n)
空间复杂度：O(1)
算法思路：
动态规划解法通过一次遍历数组，记录当前遇到的最低价格和最大利润，实现时间复杂度O(n)的高效解决方案。
核心思想：
1. 初始化minPrice为一个极大值，maxProfit为0
2. 遍历数组中的每个价格：
- 如果当前价格小于minPrice，更新minPrice为当前价格
- 否则，计算当前价格与minPrice的差值，如果大于maxProfit，更新maxProfit
3. 遍历结束后，返回maxProfit
复杂度分析：
- 时间复杂度：O(n)，只需遍历数组一次
- 空间复杂度：O(1)，只使用了常数额外空间，不随输入规模变化