买卖股票的最佳时机

给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出这只股票。

请设计一个算法，计算你所能获取的最大利润。

如果不能获取任何利润，返回 0。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：5
解释：在第 2 天价格为 1 时买入，在第 5 天价格为 6 时卖出，最大利润为 6 - 1 = 5。
注意不能计算 7 - 1 = 6，因为卖出必须发生在买入之后。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：价格一直下降，无法获得正利润，所以返回 0。

提示：

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

一次遍历-贪心：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = prices[0];
        int ans = 0;

        for (int i = 1; i < prices.size(); i++)
        {
            ans = max(ans, prices[i] - minPrice);
            minPrice = min(minPrice, prices[i]);
        }

        return ans;
    }
};

核心思想

如果在第 i 天卖出股票，那么为了让利润最大，买入时间一定应该选择在第 i 天之前价格最低的那一天。

所以遍历到每天的价格时，只需要维护两个信息：

• 到目前为止出现过的最低买入价格 minPrice
• 到目前为止可以获得的最大利润 ans

当前价格是 prices[i] 时，如果今天卖出，利润就是：

prices[i] - minPrice

然后用它更新最大利润。

这题最关键的观察是：

对于每一个卖出日，最优买入日一定是它之前价格最低的那一天。

因此不需要枚举所有买入日和卖出日，只需要从左到右遍历一次。

为什么买入价只维护历史最低值

假设今天价格是 prices[i]。

如果决定今天卖出，那么买入日必须在今天之前。

所有可能的利润是：

prices[i] - prices[0]
prices[i] - prices[1]
...
prices[i] - prices[i - 1]

为了让利润最大，就应该让减去的买入价格最小。

所以只需要知道：

prices[0...i - 1] 中的最小值。

这个最小值就是：

minPrice

如果今天价格更低，就更新买入价格：

minPrice = min(minPrice, prices[i]);

如果今天价格更高，就尝试今天卖出：

ans = max(ans, prices[i] - minPrice);

为什么更新顺序是先计算利润，再更新最低价

题目要求卖出必须发生在买入之后，不能在同一天买入并卖出。

所以处理第 i 天时，计算利润应该使用前 i 天的最低价格。

代码先执行：

ans = max(ans, prices[i] - minPrice);

再执行：

minPrice = min(minPrice, prices[i]);

这样 minPrice 在计算当天利润时只包含之前的价格。

即使把更新顺序交换，当前价格减去自己只会得到 0，通常也不会影响本题结果，但先计算利润再更新最低价更符合“先买入，后卖出”的题意。

为什么无法盈利时返回 0

如果股票价格一直下降，例如：

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

任意一次交易都会亏损。

题目允许不进行交易，所以最大利润不是负数，而是 0。

因此答案初始化为：

int ans = 0;

如果后续发现有盈利交易，再更新为正数。

正确性证明

我们证明：算法返回的 ans 是能够获得的最大利润。

结论 1：处理第 i 天时，minPrice 等于前 i 天中的最低价格

开始时：

minPrice = prices[0];

此时它就是前 1 天中的最低价格。

处理新的一天 i 时，代码执行：

minPrice = min(minPrice, prices[i]);

它会在之前的最低价格和今天价格之间取更小值。

所以处理完成后，minPrice 就是从第 0 天到第 i 天之间的最低价格。

由归纳可知，遍历过程中 minPrice 始终记录历史最低买入价格。

结论 2：如果第 i 天卖出，算法计算出的利润是第 i 天卖出的最大利润

如果第 i 天卖出，买入日必须位于第 i 天之前。

根据结论 1，minPrice 是之前所有价格中的最小值。

因此：

prices[i] - minPrice

就是以第 i 天为卖出日时的最大可能利润。

算法没有遗漏任何更优的买入日。

结论 3：ans 等于所有合法交易利润中的最大值

算法遍历每一个可能的卖出日 i，并计算该卖出日对应的最大利润：

prices[i] - minPrice

然后执行：

ans = max(ans, prices[i] - minPrice);

所以 ans 会保存所有卖出日对应利润中的最大值。

如果所有交易都亏损，ans 保持为初始值 0，表示选择不交易。

得出结论

由结论 1 可知，算法始终记录了正确的最低买入价格。

由结论 2 可知，对于每个卖出日，算法都计算出了该卖出日的最大利润。

由结论 3 可知，算法最终取得了所有合法交易中的最大利润，并正确处理了无法盈利的情况。

因此算法正确。

举例理解

以：

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

为例。

最终答案是：

5

对应的交易是：

价格为 1 时买入，价格为 6 时卖出

再看：

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

历史最低价不断下降，但每天卖出都会亏损。

所以 ans 始终保持为 0，最终返回 0。

复杂度分析

数组只需要从左到右遍历一次。

每一天只进行常数次比较和计算。

所以时间复杂度是：

O(n)

算法只使用 minPrice 和 ans 两个额外变量。

所以空间复杂度是：

O(1)