LeetCode 121. 买卖股票的最佳时机(Best Time to Buy and Sell Stock)
发布日期:2021-06-29 17:11:22
浏览次数:2
分类:技术文章
本文共 1610 字,大约阅读时间需要 5 分钟。
LeetCode.jpg
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。示例 1:输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。示例 2:输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
Python3 实现
动态规划
# @author:leacoder# @des: 动态规划 买卖股票的最佳时机 II (通用型) class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 result = 0 # 二维数组 # profit[i][0] 第i天 一直没有股票 的利润 # profit[i][1] 第i天 当前有股票( 前面有股票今天不卖 + 前面没股票 今天买入 ) 的利润 # profit[i][2] 第i天 之前买入现在卖了 (前面有股票 今天卖出 ) 的利润 profit = [[0 for _ in range(3)] for _ in range(len(prices))] # 第一天利润初始 profit[0][0],profit[0][1],profit[0][2] = 0, - prices[0] , 0 for i in range(1,len(prices)): profit[i][0] = profit[i - 1][0] profit[i][1] = max(profit[i - 1][1],profit[i - 1][0] - prices[i] ) profit[i][2] = profit[i - 1][1] + prices[i] result = max(result,profit[i][0],profit[i][1],profit[i][2]) return result
一次遍历 记录最小价格
# @author:leacoder# @des: 一次遍历 买卖股票的最佳时机 II # 由于一次交易操作 故可以通过记录最小价格 计算最大利润的方式class Solution: def maxProfit(self, prices: List[int]) -> int: if not prices: return 0 minprice,maxprofit = float("inf"),0 for i in range(len(prices)): minprice = min(minprice,prices[i]) # 记录当前最小 maxprofit = max(maxprofit,prices[i] - minprice) # 计算 当前最大利润(之前最大利润 与 当前价格与之前最小价格之差 的最大值) return maxprofit
GitHub链接:
知乎个人首页:简书个人首页:个人Blog:欢迎大家来一起交流学习
转载地址:https://blog.csdn.net/leacock1991/article/details/101467180 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月09日 03时41分04秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
IntelliJ IDEA - 热部署插件JRebel 安装使用教程
2019-04-30
插件GsonFormat快速实现JavaBean
2019-04-30
Java面试题全集(上)
2019-04-30
Java面试题全集(中)
2019-04-30
Java面试题全集(下)
2019-04-30
《代码整洁之道》读书笔记
2019-04-30
Java程序员从笨鸟到菜鸟之(六十七)细谈Spring(一)spring简介
2019-04-30
Java程序员从笨鸟到菜鸟之(六十八)细谈Spring(二)自己动手模拟spring
2019-04-30
Java程序员从笨鸟到菜鸟全部博客目录
2019-04-30
java程序员从笨鸟到菜鸟之(七)一—java数据库操作
2019-04-30
Java程序员从笨鸟到菜鸟之(八)反射和代理机制
2019-04-30
面试心得与总结—BAT、网易、蘑菇街
2019-04-30
Java对象初始化顺序
2019-04-30
Java开发的几个注意点
2019-04-30
我的Java后端书架 (2016年暖冬4.0版)
2019-04-30
每个程序员都必读的10篇文章
2019-04-30
也谈IO模型
2019-04-30
谈谈互联网后端基础设施
2019-04-30
Mybatis的ResultMap的使用
2019-04-30