买卖股票的最佳时间问题

力扣121、122 、123、188

Posted by songjiu on May 7, 2019

题目概述

关于力扣股票买卖最佳时间问题的整理。该系列题型就是给定一个代表股票价格的数组,通过不同时间的买卖来获取利益最大化。

Best Time to Buy and Sell Stock I

题目概述

题目分析

由于只能交易一次,因此需要找到在一个最小值与位于他后面的最大值,使得二者的差值在整个序列当中最大,因此遍历一次该数组,不断更新最小值以及最大值与最小值的差值即可。

代码

def maxProfit(self, prices: List[int]) -> int:
        min_p, max_p = sys.maxsize, 0
        for i in range(len(prices)):
            min_p = min(min_p, prices[i])
            max_p = max(max_p, prices[i] - min_p)
        return max_p

Best Time to Buy and Sell Stock II

题目概述

题目分析

该问题与题目1的区别在于,可以无限次的购买和出售股票,假设存在以下股票序列:[1,3,7]在不限制交易次数的情况下,有以下两种交易的方式: 1.在1的时候购买,7的时候卖出(即最低点购买,最高卖出)2.因为不限制交易次数,所以在获利的情况下就卖出并再次购买,此种获利情况为:1时买入,3时卖出,3时买入,7时再次卖出,即为(3-1+7-3),我们发现1、2两种交易方式获利情况相同,原因就是在一个升序的股票序列当中,获利的最大值永远是该升序的末尾-开端。因此在不限定交易次数的情况下,只需要找全部股票序列当中的升序子序列,并将其末尾与开头的差值累加即为答案。

代码

def maxProfit(self, prices: List[int]) -> int:
        res=0
        for i in range(len(prices)-1):
            if prices[i]<prices[i+1]:
                res+=prices[i+1]-prices[i]
        return res

Best Time to Buy and Sell Stock III

题目概述

题目分析

该题目与题目2有所不同,限制了交易次数为两次,因此不能采取和题目2相同的策略,因为对于两个连续的升序子序列,虽然他们的获利最大值是各自交易两次,但这也占用了两次交易的上限,因此无法判定如何选取两次交易,而使其交易利益最大化。(如序列:[1,2,4,2,5,7,2,4,9,0]当中,显然存在以下升序子序列:[1,2,4]、[2,5,7]、[2,4,9],他们分别获利3、5、7,在不限制交易次数的情况下,交易的最大获利为(3(4-1)+5(7-2)+7(9-2)),然而交易两次的最大利益并不是5+7=12,因为可以将前两个序列合并,只占用一次交易限额,而后将第二个交易限度用在第二个序列上,即(7-1)+(9-2)=13)。
因此我们考虑题目1当中的情况,同样使用迭代的方式,具体思想为:分为两次交易过程,第一次购买的价格为股票价格的最低点,第一次销售的获利为当前股票价格-第一次购买的股票价格的值,并且记录该值的最大值(与题目1当中一致),第二次购买股票的价格为:当前股票价格减去第一次股票的获利,并记录该值的最小值,第二次出售股票的获利(也是最终的获利)为:当前股票价格减去第二次购买股票的价格,并记录该值的最大值。以此迭代,最终第二次出售股票的价格就是最终结果。

代码

def maxProfit(self, prices: List[int]) -> int:
        len_prices = len(prices)
        if len(prices)==0:
            return 0
        buy1, sell1, buy2, sell2 = prices[0], 0, prices[0], 0
        for i in range(1, len_prices):
            buy1 = min(buy1, prices[i])
            sell1 = max(sell1, prices[i]-buy1 )
            buy2 = min(buy2, prices[i]-sell1)
            sell2 = max(sell2, prices[i]-buy2)
        return sell2

Best Time to Buy and Sell Stock IV

题目概述

题目分析

该问题为第三题的变体,相当于将原先的限定交易次数为2次改为了k次,这里考虑两种情况: 1.当k>=len(nums)//2的时候,因为交易一次至少需要1买1卖,而当总共的股票数目都没有限定交易次数的两倍多的时候,相当于没有限定交易次数,因此直接使用题目2的解题方法,找升序序列。
2.当k满足k<len(nums)//2的时候,此时的题目相当于第三题的变体,同样采用和第三题相同的策略,将原来的2买2卖的变量,改为k买k卖的list,同样,第一次买还是寻找股票的最小值,第一次卖的获利仍然为股票价格与购买的价格的差值的最大值,之后的1到k-1次交易,购买的价格永远等于当前的股票价格减去上一次的交易获利,而出售的价格永远等于当前的股票价格减去本次购买股票的价格,这样迭代,在list当中的第k-1次出售就是最终的最大值。

代码

if k==0:
            return 0
        n, res = len(prices), 0
        if n < 2:
            return 0
        if k > n //2:  # 现在这个情况,就相当于题目2
            for i in range(1, n):
                if prices[i] > prices[i-1]:
                    res += prices[i] - prices[i-1]
            return res
        buy, sell = [prices[0]] * (k ), [0] * (k )#这里将题目3当中的buy1 sell1 buy2 sell2升级为k的情况
        for price in prices:
            for j in range(0, k):
                if j==0:
                    buy[j] = min(buy[j], price)#原理不变,第0次仍然保持原状,从1到k-1开始,每次都需要依据他之前的一次交易来确定
                else:
                    buy[j]=min(buy[j],price-sell[j-1])
                sell[j] = max(sell[j], price-buy[j])  
        print(sell)
        return sell[k-1]

##Best Time to Buy and Sell Stock with Cooldown ###题目概述 ###题目分析 看了题解里 labuladong 老哥的解析,讲的真的是太好了,有了一些新的思路,实现一下感觉对这种类型的题目有了更深的理解。 ###代码

    def maxProfit(self, prices: List[int]) -> int:
        #dp[i][0,1]第i天 持有 或者 售出
        if len(prices)<2:
            return 0
        
        dp=[[0,0] for i in range(len(prices))]
        dp[0][0]=0
        dp[0][1]=-1*prices[0]
        dp[1][0]=max(dp[0][0],prices[1]-prices[0])
        dp[1][1]=max(dp[0][1],-1*prices[1])
        for i in range(2,len(prices)):
            dp[i][0]=max(dp[i-1][0],prices[i]+dp[i-1][1])#要么上一轮就空仓 要么是卖
            dp[i][1]=max(dp[i-1][1],dp[i-2][0]-prices[i])#要么上一轮就满仓 要么是买
        #print(dp)
        return dp[-1][0]