leetcode第一百二十二题——买卖股票的最佳时机二
2020-02-16 本文已影响0人
不分享的知识毫无意义
这道题很有意思,不限买卖次数,但是不能连续买卖,就是说你不能第一天买了,第二天没卖又买,也就是买之前先卖掉,今天可以再买,这样的话给这道题创造了一点发挥的空间。
1.题目
原题:
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
例子:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
2.解析
这道题,思路很明显了,可以买卖无数次,一天内可买可卖可休市。
(1)累加法
累加法的思路很简单,你每天都买都卖,最后就把极大值极小值找到了。
什么意思呢,按照例子,股票价格是[1,2,3,4,5],理论上最优是5-1=4,现在呢是这么算(2-1)+(3-2)+(4-3)+(5-4)=(5-1)=4。这个思路比较简单,就不多说了。
(2)最小值更新法
这个方法是我自己起的名字,具体思路是设置一个最小值,首先设置最小值为第一天的值,然后随后当第二天价格大于第一天的时候,进行买卖,同时将最小值更新为第二天的值,相当于修改了买入期,如果小于则更新最小值和当前值为较小值,因为那天显然不适合买卖了。这个代码在下边有更新。
3.python代码
class Solution:
def maxProfit(self, prices):
if not prices or len(set(prices)) == 1:
return 0
m = len(prices)
res = 0
minj = prices[0]
for i in range(1, m):
if prices[i] > minj:
res += prices[i] - minj
minj = prices[i]
else:
minj = min(minj, prices[i])
return re