121. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机

题目描述

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

核心思考：一次遍历

要在某一天卖出股票获利最大，必须在这一天之前的历史最低点买入。

因此，我们可以在一次遍历数组的过程中，维护两个变量：

1. min_：用来记录到目前为止遇到的最低股票价格。
2. ans：用来记录到目前为止产生的最大利润。

对于每一天的价格 x，我们先尝试用当天的价格减去历史最低价 x - min_，与已有的最大利润进行对比更新。最后再更新当前的最低价格，这样就能求得整个周期内的最大收益。

解题思路 (Python)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        min_ = prices[0]
        for x in prices:
            ans = max(ans, x - min_)
            min_ = min(min_, x)
        return ans

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 为数组的长度。只需要遍历一次数组即可。
• 空间复杂度：$O(1)$，只需要常数级别的变量保存最低价格和最大利润。