剑指 Offer 63. 股票的最大利润-leetcode 题目难度:中等原题链接[1]今天

题目难度: 中等
原题链接[1]
今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
【剑指 Offer 63. 股票的最大利润-leetcode】这道题是经典的股票问题, 以它为基础可以延伸很多扩展问题, 我之前也写过整个股票系列, 一共 6 道题目, 大家感兴趣的话在公众号里回复股票就能看到了~
题目描述假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

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 = 0mn = float('inf')for p in prices:mn = min(mn, p)res = max(res, p - mn)return res

参考资料[1]
原题链接: