LeetCode日常-简单-121-买卖股票的最佳时机

本文最后更新于：2020年9月27日 晚上

题目

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

自解

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        min_befor = prices[0]
        max_profit = 0
        for i in prices:
            #  记下当前位置之前最少的数
            min_befor = min(i, min_befor)
            #  如果过去最低点买入，今天卖出的话会不会超过最大的利润记录，会则更新记录
            max_profit = max(max_profit, i-min_befor)
        return max_profit

时间复杂度：O(n)

官方思路

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

  1. 动态规划做题步骤

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

  2. 本题思路
    其实方法一的思路不是凭空想象的，而是由动态规划的思想演变而来。这里介绍一维动态规划思想。
    dp[i]表示前 i 天的最大利润，因为我们始终要使利润最大化，则：
    　　　　　　　　dp[i]=max(dp[i−1], prices[i]−minprice)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution:
        def maxProfit(self, prices: List[int]) -> 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)