121. 买卖股票的最佳时机

题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

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

示例 2：

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

提示：

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

方法1

遇到这题，第一反应是动规，设S[i]为第 i 天买入股票能赚的最大利润，然后找到后面某天比第 i 天股价高，假设为第 j 天，那么有状态转移方程 S[i] = S[j]+prices[j]-prices[i]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        S = [0]*n
        for i in range(n-2, -1, -1):
            for j in range(i+1, n):
                if prices[j] >= prices[i]:
                    S[i] = S[j]+prices[j]-prices[i]
                    break
        return max(S)

结果这个方案居然超时了。。。

方法2

于是考虑 O(n) 的算法，我们可以用min_L[i] 维护第 i 天以前的最低价，用max_L[i] 维护第 i 天以前的最高价。
然后遍历 max_L[i]-min_L[i] 即可得到最优利润差。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        min_L = [0]*n
        max_L = [0]*n
        min_L[0] = prices[0]
        max_L[n-1] = prices[n-1]
        for i in range(1, n):
            min_L[i] = min(min_L[i-1], prices[i])
            max_L[n-1-i] = max(max_L[n-i], prices[n-1-i])
        max_val = 0
        for i in range(n):
            max_val = max(max_val, max_L[i]-min_L[i])
        return max_val

方法3

对于这种要找前后差最大的题，我们可以锁定最小值，然后用今天的股价减去最小值，这样也一定能获得最优解。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_val = 0
        min_price = prices[0]
        for i in range(len(prices)):
            min_price = min(min_price, prices[i])
            max_val = max(max_val, prices[i]-min_price)
        return max_val