[121] 买卖股票的最佳时机 (Best Time to Buy and Sell Stock)

难度：简单 | 标签：数组、动态规划、贪心

题目描述

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

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

示例 1：

输入： [7,1,5,3,6,4] 输出： 5 解释： 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

解法：一次遍历 / 贪心 (One Pass) —— 推荐 ✅

我们不需要对比每一天，只需要在遍历过程中维护两个变量：

1. min_price：历史最低价（截至当前天数）。
2. max_profit：历史最大利润。

核心逻辑： 假设我在第 i 天卖出，那么我一定希望是在第 i 天之前的 最低点 买入的。 所以，我们在遍历每一天时：

• 先更新 min_price：看看今天是不是比以前更便宜，如果是，就更新最低价。
• 再更新 max_profit：计算（今天价格 - 历史最低价），如果比之前的利润高，就更新最大利润。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price = INT_MAX; // 初始化为无穷大
        int max_profit = 0;      // 初始化为 0
        
        for(int i = 0; i < prices.size(); i++) {
            // 1. 贪心策略：记录目前为止遇到的最低价格
            if(prices[i] < min_price) {
                min_price = prices[i];
            }
            // 2. 贪心策略：计算如果在今天卖出（假设在上面的最低价买入）能赚多少
            else if(prices[i] - min_price > max_profit) {
                max_profit = prices[i] - min_price;
            }
        }
        return max_profit;
    }
};

(注：代码逻辑完全等同于使用了 max/min 函数的写法，展开写 if-else 有时运行效率略微更高，逻辑更清晰)

复杂度分析

• 时间复杂度：

  只需要遍历一次数组。

• 空间复杂度：

  只使用了两个常数变量。

易错点分析

1. 初始化问题：

   min_price 必须初始化为最大整数 (INT_MAX)，否则第一个价格可能无法更新它。

   max_profit 初始化为 0，因为如果没有利润，题目要求返回 0。

2. 逻辑顺序：

   虽然先更新 min_price 还是先计算 max_profit 在这道题里影响不大（因为同一天买卖利润为0），但逻辑上理解为“先看今天是不是最低买入点，如果不是，再看今天是不是最高卖出点”比较顺畅。