买卖股票的最佳时机

Leetcode Link: 121. 买卖股票的最佳时机 - 力扣（LeetCode）

题目

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

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

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

本题的特点是只能买卖一次！

解法一

思路：暴力解法，只能买卖一次，两个for就搞定了，超时

题解：时间$O(N^2)$， 空间$O(1)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i, buy in enumerate(prices): # 遍历买入
            for sell in prices[i:]:      # 遍历卖出
                res = max(sell - buy, res)
        return res

解法二

思路：贪心算法

实际上，在买卖股票时，我们总是希望能够在更低的价格时购买到股票。所以我们贪心的点在于，只要当前价格比我们买入的价格低，我们就买进。

或者可以这样想，我们什么时候会卖出股票？考虑一般情况，当我们的亏本的前一天，我们怎么样都要买股票，因为我们只想赚钱，不想赔钱。所以只要要赔钱的时候，我们就从新买入，跟之前的结果比较，找到最大。这也是一种贪心的思路

题解：时间$O(N)$， 空间$O(1)$

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        buy = prices[0]
        for val in prices[1:]:
            if val < buy:
                buy = val
            res = max(val-buy, res)
        return res

解法三

思路：动态规划 todo 没看懂，暂时不会

也不会暴力递归怎么做

题解：

启发和联系