温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

LeetCode中如何计算股票的最大利润

发布时间:2021-12-15 14:15:03 来源:亿速云 阅读:207 作者:小新 栏目:大数据

这篇文章给大家分享的是有关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。

               

题目思考

  1. 只能买卖一次, 要求最大利润, 有没有什么直观思路, 比如贪心法?
               

解决方案

               

思路

  • 因为只能买卖一次, 所以我们必须要保证买卖的那次收益最大, 这才是最佳时机, 这就要用到贪心的思路
  • 我们可以维护一个当前的最小值, 然后遍历整个数组, 每次都用当前值减去最小值, 如果收益比最终结果大的话, 就更新最终结果, 这样最终结果一定是最大的收益
  • 注意如果当前值比最小值小的话, 也要更新最小值, 意味着之后的遍历要以更新后的最小值作为买入起点
               

复杂度

  • 时间复杂度 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中如何计算股票的最大利润 ”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI