买卖股票的最佳时机
資深大佬 : zzzrf 3
假设有一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。
→在线评测地址
样例 1
输入: [3, 2, 3, 1, 2] 输出: 1 说明：你可以在第三天买入，第四天卖出，利润是 2 - 1 = 1 样例 2
输入: [1, 2, 3, 4, 5] 输出: 4 说明：你可以在第 0 天买入，第四天卖出，利润是 5 - 1 = 4 样例 3
输入: [5, 4, 3, 2, 1] 输出: 0 说明：你可以不进行任何操作然后也得不到任何利润 算法：贪心
很容易想到的贪心算法。对于每一天的价格，我考虑在那天之前的最低价买入，看看是不是能跟新答案。
- 我们利用一个单元去保存前缀最小值，或者后缀最大值。以下以前缀最小值 low 为例。
- 若当前的 prices[i]−low 能更新答案，则更新
- low=min(prices[i],low) ，继续跟新最小值即可。
复杂度分析
- 时间复杂度 O(n)
- 扫描整个数组即可
- 空间复杂度 O(1)
- 常数空间
代码
public class Solution { /** * @param prices: Given an integer array * @return: Maximum profit */ public int maxProfit(int[] prices) { // write your code here if (prices == null || prices.length == 0) { return 0; } int minPrice = Integer.MAX_VALUE; //just remember the smallest price int maximumProfit = 0; for (int i : prices) { minPrice = i < minPrice ? i : minPrice; maximumProfit = (i - minPrice) > maximumProfit ? i - minPrice : maximumProfit; } return maximumProfit; } } 题解参考
大佬有話說 (14)