UI Automator 图像处理 VBA 金融信贷 algorithm csv build routes laravel4 xsd jwt ip 网页后台模板 bootstrap模板 web前端开发实战项目 广告投放系统源码 jquery去掉空格 删除数组第一个元素 matlab四舍五入 input取消边框 flutter 缺点 python使用教程 pythonapi python搭建环境 java集合框架 java使用正则表达式 php开发实例 python源码 matlab2016a安装教程 电池救星 图片批量处理工具 hexworkshop 如何给黑白照片上色 远程桌面管理软件 ps水平翻转快捷键 ios12录屏 lol无限视野 鼠标速度怎么调 田字格字体 键盘打字手指口诀
当前位置: 首页 > 学习教程  > python

【Leetcode】122. 买卖股票的最佳时机 II(Best Time to Buy and Sell Stock II)

2021/2/8 10:44:10 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

No122. 买卖股票的最佳时机 II 题目 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。 注意:你不能同时参与多笔交易…

No122. 买卖股票的最佳时机 II

题目

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例1

  • 输入: [7,1,5,3,6,4]
  • 输出: 7
  • 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例2

  • 输入: [1,2,3,4,5]
  • 输出: 4
  • 解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
    注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
    因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例3

  • 输入: [7,6,4,3,1]
  • 输出: 0
  • 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路:

总体思路和121题保持相同

  1. 异常值判空
  2. 变量说明:
  • res变量用于存储结果即总体利润;
  • maxV变量用于存储当前关注的局部最大利润;
  • left和right表示局部最大利润的左右值(均为闭),初始化为第一个元素;
  1. 整体思路:
    对prices中第一个元素之后的元素进行循环,由于left<=right,所以考虑当前值x和左右值的四种关系:
  • x < left时, 说明应该清仓,此时操作:res加上maxV,left、right、maxV进行初始化;
  • left <= x <right时,也说明应该清仓,所以这种情况可以和上面的情况进行合并;
  • x == rights时,无需清仓,继续观望,不做任何操作;
  • x > right时,无需与最大值进行比较,因为此时一定是最大,更新right和maxV;

综上循环体内只需进行两个分支操作。

最后别忘了由于直接[1,2,3,4,5]这样的直接收盘的情况,需要在返回res之前加上maxV。

代码如下:

解题代码(Python3)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if prices == []:
            return 0
        res = maxV = 0
        left = right = prices[0]
        for x in prices[1:]:
            if x > right:
                right = x
                maxV = right - left
            elif x < right:
                left = right = x
                res += maxV
                maxV = 0
        #防止直接收盘
        res += maxV
        return res

复杂度分析:

  • 时间复杂度 O(n)
  • 空间复杂度 O(1)

运行结果:

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000299.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?