Hot 100 --- 买卖股票的最佳时机

本文概览：本文讲解买卖股票的最佳时机的核心思路：每个卖出日的最优买入日就是它前面的历史最低价，一次遍历同时维护最小价格和最大利润，从 O(n²) 降到 O(n)

一、题目

买卖股票的最佳时机题目图片

二、题目分析

1. 题目要求

给定一个数组 prices，第 i 个元素代表第 i 天的股票价格。只能选择某一天买入，并在它之后的某一天卖出，求能获得的最大利润。如果不能获利，返回 0。

例子：prices = [7, 1, 5, 3, 6, 4]

0  1  2  3  4  5        ← 索引（天）
7  1  5  3  6  4        ← 价格
   ↑           ↑
  买入        卖出
（第1天,1）  （第4天,6）

最大利润 = 6 - 1 = 5

注意两条规则：

卖出必须在买入之后（不能在买入前卖出）
只能交易一次

比如不能算 7 - 1 = 6：7 在第 0 天，1 在第 1 天，这是"先卖后买"，不合法。

2. 暴力思路：枚举所有买入/卖出组合

由于卖出只能在买入之后，那就从第一天开始，枚举每个买入日、再枚举它后面的每个卖出日，算出所有利润取最大：

for (int i = 0; i < n; i++) {          // 买入日
    for (int j = i + 1; j < n; j++) {  // 卖出日
        maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
    }
}

**时间复杂度 O(n²)**：两层循环，每个买入日都要往后扫一遍所有卖出日。

3. 核心观察：暴力遍历中的无效计算

暴力慢在哪？慢在大量根本不可能成为答案的买入日也被拿来反复比较。

关键观察：如果第二天的价格比第一天低，那就肯定不会在第一天买入。为什么？后面无论哪天卖出，只要卖出价高于第一天的买入价，就必然高于第二天的价格，此时第二天买入的利润必然大于第一天买入的利润——第一天买入的所有方案都被第二天全覆盖且更差。

把这个观察推广到一般情况：

对于每一个卖出日 i，最优的买入日一定是 [0, i-1] 中价格最低的那一天。

既然如此，我们根本不需要枚举买入日。只需一直记录遍历到当天为止，前面所有天里的最低股票价格，然后用当天价格减去这个最低价，就得到了"以当天为卖出日"的最大利润：

利润更大 → 替换 maxProfit
利润不大 → 不替换

这就是贪心思想：每一步都取当前能拿到的最优解（历史最低价买入、当天卖出），最终合起来就是全局最优。这题是可以用贪心保证正确性的。

三、思路概览

public int maxProfit(int[] prices) {
    int maxProfit = 0;
    int minPrice = prices[0];
    for (int i = 1; i < prices.length; i++) {
        // 当天价格更低 → 更新历史最低价，它不可能是卖出日（没利润可算）
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else {
            // 当天价格更高 → 用历史最低价算利润，尝试更新答案
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
    }
    return maxProfit;
}

思路简要说明：

两个变量：minPrice 记录遍历到当天为止的历史最低价（初始为第 0 天价格），maxProfit 记录最大利润（初始 0，保证不获利时返回 0）
一次遍历：每个新价格只有两种情况——比历史最低价还低（更新最低价），或者更高（算利润、更新答案）
贪心本质：每个卖出日的最优买入日就是前面的历史最低价日，所以只需维护一个最低价
**时间复杂度 O(n)**：只扫一遍数组，O(n²) 降到 O(n)

四、思路详解

第一步：暴力到底重复算了什么？

把暴力解在 [7, 1, 5, 3, 6, 4] 上的部分计算列出来：

买入日 0（价格7）：卖出日 1..5 → 利润 -6, -2, -4, -1, -3
买入日 1（价格1）：卖出日 2..5 → 利润  4,  2,  5,  3
买入日 2（价格5）：卖出日 3..5 → 利润 -2,  1, -1
...

注意买入日 0 这一整行：价格 7 比第 1 天的 1 高，它算出来的所有利润都惨不忍睹。而买入日 1 的那一行，每一项都比买入日 0 对应的项正好大 6——同样的卖出日，换个更便宜的买入日，利润全面碾压。

结论：买入日价格更高的方案，被"更便宜的买入日"全面覆盖。一个卖出日真正需要配的买入日，只有它前面价格最低的那一天。枚举其它买入日全是无效计算。

第二步：为什么"历史最低价"可以代表所有买入日？

对每个卖出日 i，我们声称最优买入日是 [0, i-1] 中价格最低的那天。证明很简单：

假设卖出日 i，买入日 j 和 j'（都在 i 之前），
且 prices[j'] < prices[j]

利润(j)  = prices[i] - prices[j]
利润(j') = prices[i] - prices[j'] > 利润(j)

卖出价 prices[i] 是同一个数，买入价越低利润越大。所以比较所有买入日等价于只看最低的那个买入价——这就是 minPrice 一个变量能顶掉内层整个循环的原因。

第三步：一次遍历怎么同时维护两个信息？

遍历到第 i 天时，需要的信息有两个：

[0, i-1] 的最低价 → 用来当买入价
prices[i] - 最低价 → 以第 i 天为卖出日的最大利润

这两个信息可以顺路一起维护：

来到第 i 天：
  if  prices[i] < minPrice：
        说明第 i 天是新的历史最低 → 更新 minPrice
        （此时第 i 天自己当卖出日无利可图，跳过利润计算）
  else：
        prices[i] >= minPrice → 用 prices[i] - minPrice 算利润
        尝试更新 maxProfit

if-else 的巧妙之处：两个分支互斥且刚好覆盖所有情况——

当天是新低，它不可能贡献利润（价格 - 自己 = 0，不大于已有的 maxProfit），但它是未来卖出日的最优买入价，所以只需更新 minPrice
当天不是新低，minPrice 保持不变，当天价格减 minPrice 就是它作为卖出日的最优利润

不需要任何嵌套循环，一遍走完，minPrice 始终是"今天之前的最便宜买入价"，maxProfit 始终是"到目前为止的最大利润"。

完整执行过程

以 prices = [7, 1, 5, 3, 6, 4] 为例：

初始：minPrice = 7（第0天），maxProfit = 0

i=1, 价格1：1 < 7 → 更新 minPrice = 1
  minPrice = 1, maxProfit = 0

i=2, 价格5：5 > 1 → 利润 5 - 1 = 4 > 0 → 更新
  minPrice = 1, maxProfit = 4

i=3, 价格3：3 > 1 → 利润 3 - 1 = 2 < 4 → 不更新
  minPrice = 1, maxProfit = 4

i=4, 价格6：6 > 1 → 利润 6 - 1 = 5 > 4 → 更新
  minPrice = 1, maxProfit = 5

i=5, 价格4：4 > 1 → 利润 4 - 1 = 3 < 5 → 不更新
  minPrice = 1, maxProfit = 5

遍历结束 → 返回 5 ✓
（对应第1天买入价1，第4天卖出价6）

再走一个递减数组 [7, 6, 4, 3, 1] 的例子（验证不获利的情况）：

初始：minPrice = 7，maxProfit = 0

i=1, 价格6：6 < 7 → minPrice = 6
i=2, 价格4：4 < 6 → minPrice = 4
i=3, 价格3：3 < 4 → minPrice = 3
i=4, 价格1：1 < 3 → minPrice = 1

全程走的是 if 分支，maxProfit 从未被更新 → 返回 0 ✓
（一直跌，怎么买都亏，不如不交易）