Q121-买卖股票的最佳时机-简单-动态规划

121. 买卖股票的最佳时机

Question

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

Example 1:

输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

Example 2:

输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

Approach 1: 一次遍历

股票问题一共有六道：买卖股票的最佳时机（1，2，3，4）、含冷冻期、含手续费。本题是第一道，属于入门题目。

考虑买入股票是在[0,i-1]天内的最低点买入，只用遍历一次，计算哪天卖出利润最大即可

class Solution:
    def maxProfit(self, prices) -> int:
        inf = int(1e9)
        minprice = inf
        maxprofit = 0
        for price in prices:
            maxprofit = max(price - minprice, maxprofit)
            minprice = min(price, minprice)
        return maxprofit


def main():
    nums = [7,1,5,3,6,4]
    solution=Solution().maxProfit(nums)
    print(solution)


if __name__ == "__main__":
    main()

复杂度分析

• 时间复杂度 O(N)： 线性遍历数组 nums
• 空间复杂度 O(1)： 使用常数大小的额外空间。

Approach 2: 动态规划

动态规划一般分为一维、二维、多维（使用状态压缩），对应形式为 、、二进制。

1. 动态规划做题步骤

• 明确 应该表示什么（二维情况：）；
• 根据 和 的关系得出状态转移方程；
• 确定初始条件，如 。

2. 本题思路

其实方法一的思路不是凭空想象的，而是由动态规划的思想演变而来。这里介绍一维动态规划思想。

表示前 天的最大利润，因为我们始终要使利润最大化，则：

class Solution:
    def maxProfit(self, prices) -> int:
        n = len(prices)
        if n == 0: return 0 # 边界条件
        dp = [0] * n
        minprice = prices[0]

        for i in range(1, n):
            minprice = min(minprice, prices[i])
            dp[i] = max(dp[i - 1], prices[i] - minprice)

        return dp[-1]

复杂度分析

• 时间复杂度 O(N)
• 空间复杂度 O(N)