这篇文章给大家分享的是有关LeetCode中如何计算股票的最大利润 的内容。小编觉得挺实用的，因此分享给大家做个参考，一起跟随小编过来看看吧。
题目描述
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
-
0 <= 数组长度 <= 10^5
题目样例
示例
-
输入: [7,1,5,3,6,4]
-
输出: 5
-
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
-
输入: [7,6,4,3,1]
-
输出: 0
-
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
题目思考
-
只能买卖一次, 要求最大利润, 有没有什么直观思路, 比如贪心法?
解决方案
思路
-
因为只能买卖一次, 所以我们必须要保证买卖的那次收益最大, 这才是最佳时机, 这就要用到贪心的思路 -
我们可以维护一个当前的最小值, 然后遍历整个数组, 每次都用当前值减去最小值, 如果收益比最终结果大的话, 就更新最终结果, 这样最终结果一定是最大的收益 -
注意如果当前值比最小值小的话, 也要更新最小值, 意味着之后的遍历要以更新后的最小值作为买入起点
复杂度
-
时间复杂度 O(N): 需要遍历整个数组一遍 -
空间复杂度 O(1): 只需要维护常数个变量
代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
res = 0
mn = float('inf')
for p in prices:
mn = min(mn, p)
res = max(res, p - mn)
return res感谢各位的阅读！关于“LeetCode中如何计算股票的最大利润 ”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！
原创文章，作者：bd101bd101，如若转载，请注明出处：https://blog.ytso.com/tech/opensource/223564.html