一次遍历拿下 LeetCode 股票题

LeetCode 121″买卖股票的最佳时机”是一道经典的数组与贪心题。题目看起来需要同时选择买入日和卖出日，但真正求解时并不需要枚举所有组合。只要在遍历过程中维护此前出现过的最低价格，就能用一次遍历得到最大利润。

本文将从暴力枚举入手，推导贪心解法，并重点解释”为什么最低买入价必须出现在卖出日之前”。

题目说明

给定数组 prices，其中 prices[i] 表示某只股票第 i 天的价格。只能选择一天买入，并在未来的某一天卖出，求一次交易能够获得的最大利润。如果无法获得正利润，返回 0。

输入：prices = [7, 1, 5, 3, 6, 4]
输出：5
解释：第 2 天以 1 买入，第 5 天以 6 卖出，利润为 6 - 1 = 5。

本题有三个关键限制：

• 最多只能完成一次买入和一次卖出
• 必须先买入，再卖出
• 可以选择不交易，此时利润为 0

暴力枚举

最直观的思路是枚举所有买卖组合：外层选择买入日，内层选择其后的卖出日，计算两天的价格差并更新最大利润。

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;

        for (int buy = 0; buy < prices.length; buy++) {
            for (int sell = buy + 1; sell < prices.length; sell++) {
                maxProfit = Math.max(
                        maxProfit,
                        prices[sell] - prices[buy]
                );
            }
        }

        return maxProfit;
    }
}

这种写法容易理解，但时间复杂度为 O(n²)。当数组长度较大时，重复比较会造成明显性能问题。

贪心算法的核心思想

假设遍历到第 i 天，并把当天价格 prices[i] 看作卖出价。为了让利润最大，买入价应该选择第 i 天之前出现过的最低价格。

因此只需要维护两个变量：

• minBuyPrice：当前日期之前出现过的最低价格
• maxProfit：遍历过程中得到的最大利润

对于每一个当前价格，执行以下操作：

当前利润 = 当前价格 - 历史最低价格
最大利润 = max(最大利润, 当前利润)
历史最低价格 = min(历史最低价格, 当前价格)

这是一种贪心选择：当卖出日期固定时，更低的买入价格一定不会让结果变差。因此，只需要保留历史最低价，其他更高的买入价格都可以舍弃。

示例演算

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

遍历结束后，最大利润为 5，对应在价格为 1 时买入，在价格为 6 时卖出。

需要注意，价格 1 出现后，后续不需要再考虑价格 7 作为买入价。因为对于任何未来的卖出价格，以 1 买入都比以 7 买入更优。

为什么不能直接用最高价减最低价？

有人可能会先找到数组中的最低价和最高价，再计算二者之差。但这种方法忽略了”先买后卖”的时间约束。

例如：

prices = [7, 6, 4, 3, 1]

全局最高价是 7，最低价是 1，但 7 出现在 1 之前。如果计算 7 - 1 = 6，相当于先以 1 买入，再回到过去以 7 卖出，显然不符合题意。

正确做法是：每次把当天作为卖出日，只使用当天之前的最低价格计算利润。这样天然保证买入日期早于卖出日期。

为什么要先计算利润，再更新最低价？

代码从第二天开始遍历，并按照以下顺序执行：

1. 使用历史最低价计算当天卖出的利润
2. 更新最大利润
3. 再使用当天价格更新最低价

这样写能让变量语义非常明确：计算第 i 天卖出利润时，minBuyPrice 只来自前 i - 1 天，严格满足”买卖发生在不同日期”的要求。

如果先更新最低价，在当前价格更低时会得到 currentProfit = 0，最终答案通常仍不会因此出错，但会把”同一天买入并卖出”混入状态含义。先计算利润再更新最低价，更符合题目约束，也更方便解释和维护。

Java 完整实现

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }

        int minBuyPrice = prices[0];
        int maxProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            // 当前价格作为卖出价，买入价只能来自此前日期
            int currentProfit = prices[i] - minBuyPrice;
            maxProfit = Math.max(maxProfit, currentProfit);

            // 当前价格可作为未来某一天的买入价
            minBuyPrice = Math.min(minBuyPrice, prices[i]);
        }

        return maxProfit;
    }
}

代码只遍历数组一次。minBuyPrice 保存当前日期之前的最低价格，maxProfit 保存已经考察过的所有合法交易中的最大利润。

边界情况

价格持续下降 ：

prices = [7, 6, 4, 3, 1]

所有卖出利润都小于或等于零。由于 maxProfit 初始化为 0，最终返回 0，表示不进行交易。

只有一个价格 ：

prices = [5]

只有一天，无法在不同日期完成买入和卖出，因此返回 0。

价格相同 ：

prices = [3, 3, 3]

任意合法交易的利润均为零，最终返回 0。

最低价出现在最后一天 ：

prices = [5, 4, 3, 2, 1]

最后一天虽然是最低价，但后面没有可供卖出的日期，所以它无法产生利润。算法只会把它保存为潜在买入价，不会凭空构造未来卖出日。

复杂度分析

• 时间复杂度：O(n)，只遍历价格数组一次
• 空间复杂度：O(1)，只使用常数个变量

与暴力解法相比，贪心算法把时间复杂度从 O(n²) 降低到了 O(n)。