121. 买卖股票的最佳时机

Difficulty
easy
Tags
动态规划
贪心算法
URL
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
Star
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
提示：
  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

法1 贪心算法

思路
从前到后遍历pricess数组，每一步只取最大利润值
题解
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minVal = prices[0]
        maxProfit = 0

        for i in range(len(prices)):
            if prices[i] < minVal:
                minVal = prices[i]
            if prices[i] - minVal > maxProfit:
                maxProfit = prices[i]-minVal
        return maxProfit

法2 动态规划

思路
包括买、卖两种状态。所以采用二维数组
notion imagenotion image
dp[0][i]: 表示第i天持有股票的最小消费（也就是剩余的最大金额）。可能是第i天买的，也可能是之前买的，所以dp[0][i] = min(dp[0][i-1], prices[i])
dp[1][i] 表示第i天的最大利润。可能是第i天卖掉的，也可能是之前卖掉的。所以dp[1][i] = max(dp[1][i-1], prices[i]-dp[1][i-1]
💡
dp[0]这一维数组始终存放着对当天来说买入股票后剩余的最大金额。 dp[1]这一维数组通过max()始终保持着对当前来说最大的利润。如果当天卖的话，其实是用之前（或当前）剩余的最大金额 dp[i-1][0]+ 当天卖出的价钱prices[i]
题解
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [[0] * len(prices) for _ in [0, 1]]
        dp[0][0] = -prices[0]
        print(dp)
        for i in range(1, len(prices)):
            dp[0][i] = min(dp[0][i-1], prices[i])
            dp[1][i] = max(dp[1][i-1], prices[i]+dp[0][i-1])
        
        print(dp)
        return dp[1][-1]
注意：dp[1][i] = max(dp[1][i-1], prices[i]+dp[0][i-1]) 这一行代码中，计算当天卖出的价钱的时候 采用前一天的最大余额dp[i-1][0]加当前的股票价钱prices[i]，其实用当天的最大余额dp[i][0]亦可。我的理解如下：
最大余额肯定是越来越大的。
  • 如果当天进行了买入操作，采用当天的余额dp[i][0]+当天的股票价钱prices[i] 最后必然等于0, 也就是说，如果采用之前的余额，计算得到的利润必然是负数，因为max(0,负数）操作，最后得到的还是 0.
  • 如果当天没有进行买入操作，那么dp[i-1][0] == dp[i][0], 使用前一天还是当天是一样的
最后，理解取出两个数组各自代表的含义后，即可进行程序优化。优化如下：
  • 使用一个变量 buy来保持 对当前来说 买入股票后剩余的最大金额（剩余最大，其实就是买股票花费最小）。
  • 使用另一个变量 sell来保持对当前来说 最大的利润。
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = -prices[0]
        sell = 0
        for price in prices:
            buy = max(buy, -price)       # (当天不买，当天买了)
            sell = max(sell, buy+price)  # (当天不卖，当天卖了)
        
        return sell
📎
Python 二维数组的创建：dp = [[0] * len(prices) for _ in [0, 1]] 里面使用 * ，外层使用列表表达式