买卖股票的最佳时机

🟢 Easy · 🏷️ 数组、动态规划 · LeetCode#121

📖 题目

prices[i] 是第 i 天的股价，只能买一次、卖一次（先买后卖），求最大利润；不能获利就返回 0。

输入	输出	说明
[7,1,5,3,6,4]	5	第2天买入(1)，第5天卖出(6)
[7,6,4,3,1]	0	一直跌，不买最好

💡 思路

站在第 i 天想"如果今天卖出，利润最大是多少"——答案只取决于今天之前出现过的最低价，跟今天之后会发生什么无关。所以只需要一次遍历，边走边维护一个历史最低价 left_min，每天用当天价格减去这个最低价，跟当前最大利润比较，取较大的。

💻 代码

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

时间复杂度 O(n)，一次遍历；空间复杂度 O(1)，只用了两个变量。"遍历中维护一个历史最值"是数组题里很常见的技巧。