[121][简单][动态规划] 买卖股票的最佳时机

题目描述

121. 买卖股票的最佳时机

给定一个数组，它的第 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。

解题思路

一次遍历

其实就如同炒股票一样, 我们要找的其实就是波段的最低点和最高点, 他们之间的差就是利润, 找到最大的那一个.

我们知道小波段可以合成大波段, 反映的本题中, 就是对于一个区段低点, 从前向后遍历, 如果它之后出现过更低的点, 那么当前这个低点可能的最大利润对应的卖出高点, 一定在这个更低点之前, 否则在这个更低点买入利润更大. 因此从前向后遍历, 不断计算利润, 直到遇到更低的点, 更换到新的最低点后继续计算.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n, max_profit = len(prices), 0
        if n < 2:
            return max_profit

        lowest = prices[0]
        for i in range(1, n):
            if prices[i] < lowest:
                lowest = prices[i]
            else:
                max_profit = max(max_profit, prices[i] - lowest)
        return max_profit

动态规划

对于买卖股票这一系列的题目, 都可以考虑使用动态规划来做.

本题要求股票只能买卖一次, 且股票状态只有持有和空仓两种, 因此可以创建两个数组, 分别记录对应状态第$i$天所能获取的最大利润.

对于持有, 其实就是买入后的状态, 对应数组中的值一定是负的, 因此只有买入没有卖出. 持有分为之前买入和当天买入, 所以状态转移方程为:

$\text{dp1}[i] = \max(\text{dp1}[i - 1], -\text{prices}[i])$

其实就是在同上不停寻找最低点.

空仓状态同理, 分为之前也是空仓, 以及今天卖出导致空仓, 状态转移方程为:

$\text{dp2}[i] = \max(\text{dp2}[i - 1], \text{dp1}[i - 1] + \text{prices}[i])$

$\text{dp2}[i]$一直记录的都是当前$i$时刻的最大利润.

考虑边界条件, $\text{dp1}[0]$的值为$-\text{prices}[0]$, 持仓就需要买入嘛; $\text{dp2}[0] = 0$. 最后的结果为$\text{dp2}[-1]$.

状态转移方程只使用了$i-1$天的结果, 可以使用滚动来节省空间.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0

        cache1, cache2 = -prices[0], 0  # cache1: 持有, cache2: 空仓
        for i in range(1, n):
            cache2 = max(cache2, cache1 + prices[i])
            cache1 = max(cache1, -prices[i])
        return cache2