LeetCode121（买卖股票的最佳时机1）

发表于 | 分类于 ，

题目：

　　给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

思路：

　　我们需要找到数组中最低的波谷和之后最高的波峰。我们需要维护一个最低股票价格minPrice和最大收益maxPrice，并实时更新。minPrice很容易求出，而
maxPrice=max(前一天的最大收益，今天的股票价格-minPrice)。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
// DP
public static int maxProfit1(int[] prices) {
	int maxPro = 0;
	int minPrice = Integer.MAX_VALUE;
	for(int num:prices) {
		if (num < minPrice) {
			minPrice = num;
		}else {
			maxPro = Math.max(maxPro, num-minPrice);
		}
	}
	return maxPro;
}

复杂度分析：

动态规划：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

原题链接：

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/