跳到主要内容

LeetCode 121. 买卖股票的最佳时机

本节目标

用前缀最低价格表示此前唯一值得保留的买入选择。

这是单序列扫描与边界的前缀最优模型。与下一题不同，这里只允许一次买卖，因此每个卖出日只需搭配此前最低买入价。

题意与约束​

给定每日股价，可选择至多一次先买后卖的交易，返回最大收益；若始终下降则不交易并返回 0。

直接思路与瓶颈​

枚举买入日与卖出日需要 O(n^2)。实际上，固定卖出日后，所有更高的历史价格都不可能比历史最低价更优。

贪心模型与算法推导​

从左到右维护 lowest，表示当前日之前（含当前日）的最低价格。到达价格 price 时，用 price-lowest 尝试更新 best，再继续维护最低价格。状态只保留一个前缀最优值。

正确性依据​

扫描到第 i 天时，lowest 是前缀中最小价格。任何以第 i 天卖出的最优交易必从这个最低价买入，否则替换买入日只会使收益更大或不变。因此 best 始终是所有已扫描卖出日的最优收益；扫描结束即得到全局最优。

样例执行过程​

对 [7,1,5,3,6,4]，先得到 lowest=7，到 1 更新为 1；价格 5 产生收益 4，价格 6 产生收益 5，最终返回 5。[7,6,4,3,1] 不会产生正收益，保留初值 0。

代码实现​

C++17
#include <algorithm>
#include <limits>
#include <vector>

using namespace std;

class Solution {
public:
    int maxProfit(vector<int> prices) {
        int lowest = numeric_limits<int>::max();
        int best = 0;
        for (int price : prices) {
            lowest = min(lowest, price);
            best = max(best, price - lowest);
        }
        return best;
    }
};

复杂度分析​

只扫描一次，时间 O(n)，额外空间 O(1)。

边界与易错点​

  • 卖出日必须晚于买入日；更新顺序不能使用未来价格。
  • 单日或空价格序列没有可完成交易，收益为零。
  • 这是一次交易，不要累加多段上涨。

模式迁移​

“固定当前结束位置，保留此前最优起点”也适用于最大差值、最小前缀和等问题；允许多次交易时应转到下一题的收益分解。