【Leetcode 热题 100】121. 买卖股票的最佳时机
问题背景
给定一个数组
p
r
i
c
e
s
prices
prices，它的第
i
i
i 个元素
p
r
i
c
e
s
[
i
]
prices[i]
prices[i] 表示一支给定股票第
i
i
i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回
0
0
0。
数据约束
- 1 ≤ p r i c e s . l e n g t h ≤ 1 0 5 1 \le prices.length \le 10 ^ 5 1≤prices.length≤105
- 0 ≤ p r i c e s [ i ] ≤ 1 0 4 0 \le prices[i] \le 10 ^ 4 0≤prices[i]≤104
解题过程
整体是贪心算法，思想是维护好前缀最小值，然后不断更新最大差值即可。
具体实现
class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int res = 0;
for(int price : prices) {
res = Math.max(res, price - min);
min = Math.min(min, price);
}
return res;
}
}