算法训练Day49 | Leetcode121. 买卖股票的最佳时机(只能买卖一次);LeetCode122. 买卖股票的最佳时机II(可以买卖多次)

发布于:2022-11-09 ⋅ 阅读:(860) ⋅ 点赞:(0)

目录

Leetcode121. 买卖股票的最佳时机

方法一:暴力解法

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获

方法二:贪心算法

1. 思路

2. 代码实现

3. 复杂度分析

方法三:动态规划

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获

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

1. 思路

2. 代码实现

3. 复杂度分析

4. 思考与收获


Leetcode121. 买卖股票的最佳时机

 链接:121. 买卖股票的最佳时机 - 力扣(LeetCode)

方法一:暴力解法

1. 思路

因为只能买一次,卖一次,所以这道题目最直观的想法就是暴力找最优间距,外层for loop从头到尾遍历元素,内层for loop从i之后遍历元素;

2. 代码实现

# 方法一:暴力解法
# time:O(N^2);space:O(1)
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        result = 0
        for i in range(len(prices)-1):
            for j in range(i+1,len(prices)):
                result = max(result,prices[j]-prices[i])
        return result

3. 复杂度分析

  • 时间复杂度:O(N^2)

    其中,N为prices数组的长度;两层for loop的时间复杂度为O(N^2);

  • 空间复杂度:O(1)

    只有result一个变量储存,为常数级的空间复杂度

4. 思考与收获

  1. 此方法在LeetCode提交中超时了;

方法二:贪心算法

1. 思路

因为股票就买卖一次,那么贪心的想法很自然就是取最左最小值,取最右最大值,那么得到的差值就是最大利润。

2. 代码实现

# 方法二:贪心做法
# time:O(n);space:O(1)
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        low = float("inf")
        result = 0
        for i in range(len(prices)):
            low = min(low,prices[i]) # [0,i]位置的最小值
            result = max(result,prices[i]-low) # 目前可以得到的最大利润
        return result

3. 复杂度分析

  • 时间复杂度:O(N)

    其中N为prices的长度;需要遍历一遍整个数组,因此复杂度为O(N);

  • 空间复杂度:O(1)

    只有两个变量储存信息,分别是low和result,常数级的空间复杂度;

方法三:动态规划

1. 思路

动规五部曲分析如下:

1.1 确定dp数组及下标的含义

  • dp[i][0]

    dp[i][0] 表示第i天持有股票所得最多现金 ,这里可能有同学疑惑,本题中只能买卖一次,持有股票之后哪还有现金呢?其实一开始现金是0,那么加入第i天买入股票现金就是 -prices[i], 这是一个负数;

  • dp[i][1]

    dp[i][1] 表示第i天不持有股票所得最多现金,注意这里说的是“持有”,“持有”不代表就是当天“买入”!也有可能是昨天就买入了,今天保持持有的状态,很多同学把“持有”和“买入”没分区分清楚,在下面递推公式分析中,我会进一步讲解。

1.2 确定递推公式

  1. 如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来
    • 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
    • 第i天买入股票,所得现金就是买入今天的股票后所得现金即:-prices[i]

那么dp[i][0]应该选所得现金最大的,所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

  1. 如果第i天不持有股票即dp[i][1], 也可以由两个状态推出来
    • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
    • 第i天卖出股票,所得现金就是按照今天股票佳价格卖出后所得现金即:prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的,dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

1.3 dp数组如何初始化

由递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出其基础都是要从dp[0][0]和dp[0][1]推导出来;

  • 那么dp[0][0]表示第0天持有股票,此时的持有股票就一定是买入股票了,因为不可能有前一天推出来,所以dp[0][0] = - prices[0];
  • dp[0][1]表示第0天不持有股票,不持有股票那么现金就是0,所以dp[0][1] = 0;

1.4 确定遍历顺序

从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的,那么一定是从前向后遍历;

1.5 举例推导dp数组

以示例1,输入:[7,1,5,3,6,4]为例,dp数组状态如下

dp[5][1]就是最终结果。为什么不是dp[5][0]呢?因为本题中不持有股票状态所得金钱一定比持有股票状态得到的多!

2. 代码实现

# 动态规划 写法一
# time:O(N);space:O(N)
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # dp定义:
        # dp[i][0] 第i天持有股票所得最多的现金
        # dp[i][1] 第i天不持有股票所得最多的现金
        # 初始化
        dp = [[0]*2 for _ in range(len(prices))]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        # 遍历
        for i in range(1,len(prices)):
            # 递推公式
            dp[i][0] = max(dp[i-1][0],-prices[i])
            dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])
        return dp[len(prices)-1][1]

从递推公式可以看出,dp[i]只是依赖于dp[i - 1]的状态;那么我们只需要记录 当前天的dp状态和前一天的dp状态就可以了,可以使用滚动数组来节省空间;

# 动态规划写法二 状态压缩
# time:O(N);space:O(1)
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # dp定义:
        # dp[i][0] 第i天持有股票所得最多的现金
        # dp[i][1] 第i天不持有股票所得最多的现金
        # 初始化
        dp = [[0,0],[0,0]]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        # 遍历
        for i in range(1,len(prices)):
            # 递推公式
            dp[i%2][0] = max(dp[(i-1)%2][0],-prices[i])
            dp[i%2][1] = max(dp[(i-1)%2][1],dp[(i-1)%2][0]+prices[i])
        return dp[(len(prices)-1)%2][1]

3. 复杂度分析

动态规划写法一

  • 时间复杂度:O(N)

    其中N为prices数组的长度;需要遍历整个prices数组一遍;

  • 空间复杂度:O(N)

    其中N为prices数组的长度;Dp为2*N的数组,需要空间也为O(N)级别;

动态规划写法二

  • 时间复杂度:O(N)

    其中N为prices数组的长度;需要遍历整个prices数组一遍;

  • 空间复杂度:O(1)

    只需要维护一个2*2大小的数组即可;

4. 思考与收获

  1. 这里能写出版本一就可以了,版本二虽然原理都一样,但是想直接写出版本二还是有点麻烦,容易自己给自己找bug;所以建议是先写出版本一,然后在版本一的基础上优化成版本二,而不是直接就写出版本二;

Reference:代码随想录 (programmercarl.com)

本题学习时间:60分钟。


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

 链接:122. 买卖股票的最佳时机 II - 力扣(LeetCode)

1. 思路

本题和121. 买卖股票的最佳时机 的唯一区别本题股票可以买卖多次了(注意只有一只股票,所以再次购买前要出售掉之前的股票);在动规五部曲中,这个区别主要是体现在递推公式上,其他都和121. 买卖股票的最佳时机 一样一样的;所以我们重点讲一讲递推公式。

这里重申一下dp数组的含义:

  • dp[i][0] 表示第i天持有股票所得最多现金。
  • dp[i][1] 表示第i天不持有股票所得最多现金

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来

  • 第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]
  • 第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[i - 1][1] - prices[i]

注意这里和121. 买卖股票的最佳时机 唯一不同的地方,就是推导dp[i][0]的时候,第i天买入股票的情况:在121. 买卖股票的最佳时机 中,因为股票全程只能买卖一次,所以如果买入股票,那么第i天持有股票即dp[i][0]一定就是 -prices[i];而本题,因为一只股票可以买卖多次,所以当第i天买入股票的时候,所持有的现金可能有之前买卖过的利润;那么第i天持有股票即dp[i][0],如果是第i天买入股票,所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即:dp[i - 1][1] - prices[i]。

在来看看如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来

  • 第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]
  • 第i天卖出股票,所得现金就是按照今天股票佳价格卖出后所得现金即:prices[i] + dp[i - 1][0]

注意这里和 121. 买卖股票的最佳时机 就是一样的逻辑,卖出股票收获利润(可能是负值)天经地义!

2. 代码实现

# 动态规划写法一
# time:O(N);space:O(N)
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # dp定义
        # dp[i][0] 第i天 持有股票所得最多现金
        # dp[i][1] 第i天 不持有股票所得最多现金
        # 初始化
        length = len(prices)
        dp = [[0]*2 for _ in range(length)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        # 遍历
        for i in range(1,length):
            # 递推公式,和LeetCode121唯一不同之处
            dp[i][0] = max(dp[i-1][0],dp[i-1][1]-prices[i])
            dp[i][1] = max(dp[i-1][1],dp[i-1][0]+prices[i])
        return dp[length-1][1]

同样也有滚动数组的版本:

# 动态规划写法二 状态压缩
# time:O(N);space:O(1)
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        # dp定义
        # dp[i][0] 第i天 持有股票所得最多现金
        # dp[i][1] 第i天 不持有股票所得最多现金
        length = len(prices)
        dp = [[0]*2 for _ in range(2)]
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        # 遍历
        for i in range(1,length):
            # 递推公式
            dp[i%2][0] = max(dp[(i-1)%2][0],dp[(i-1)%2][1]-prices[i])
            dp[i%2][1] = max(dp[(i-1)%2][1],dp[(i-1)%2][0]+prices[i])
        return dp[(length-1)%2][1]

3. 复杂度分析

动态规划写法一

  • 时间复杂度:O(N)

    其中N为prices数组的长度;需要遍历整个prices数组一遍;

  • 空间复杂度:O(N)

    其中N为prices数组的长度;Dp为2*N的数组,需要空间也为O(N)级别;

动态规划写法二

  • 时间复杂度:O(N)

    其中N为prices数组的长度;需要遍历整个prices数组一遍;

  • 空间复杂度:O(1)

    只需要维护一个2*2大小的数组即可;

4. 思考与收获

  1. 本题和121. 买卖股票的最佳时机 的代码几乎一样,唯一的区别在:

    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
    

    这正是因为本题的股票可以买卖多次! 所以买入股票的时候,可能会有之前买卖的利润即:dp[i - 1][1],所以dp[i - 1][1] - prices[i];想到到这一点,对这两道题理解的比较深刻了。

Reference:代码随想录 (programmercarl.com)

本题学习时间:30分钟。


本篇学习时间为1.5小时,总结字数5000+;是动态规划中一个新的专题叫做股票问题,本篇讲了只能买卖一次的情况和可以买卖多次的情况,两种只有递推公式不一样。(求推荐!)

本文含有隐藏内容,请 开通VIP 后查看