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)$，只需要常数级别的变量保存最低价格和最大利润。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

num1 num2 num3 ... numN

输入一行整数数组，以空格分隔。

完整代码：

import sys

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

def main():
    nums = list(map(int, sys.stdin.read().strip().split()))

    sol = Solution()
    result = sol.maxProfit(nums)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

echo "2 -1 3 4 -5" | python solution.py