买卖股票的最佳时机

低价买入，高价卖出。

从左到右枚举卖出价格 $prices [i]$ 。要想获得最大利润，哪天买入最好？在股票价格最低的那天买入。

注意，买入日期必须在卖出日期之前，所以我们求的是从 $prices [0]$ 到 $prices [i - 1]$ 的最小值，这可以用一个变量 $minPrice$ 维护。

由于只能买卖一次，所以在遍历中，计算 $prices [i] - minPrice$ 的最大值，就是答案。

注：下面代码中，我们先更新 $ans$ ，再更新 $minPrice$ ，以保证 $minPrice$ 在 $prices [i]$ 之前。请读者思考：更新顺序能否交换？如果一定要交易一次，即使亏钱也要交易，更新顺序能否交换？

Python 解法1C++ 解法1

python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ans = 0
        min_price = prices[0]
        for p in prices:
            ans = max(ans, p - min_price)
            min_price = min(min_price, p)
        return ans

cpp

// C++ 版待补充

C++ 解法2

cpp

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        int min_price = prices[0];
        for (int p : prices) {
            ans = max(ans, p - min_price);
            min_price = min(min_price, p);
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n)$ ，其中 $n$ 为 $prices$ 的长度。
空间复杂度： $O (1)$ 。

思考题

如果一定要交易一次，代码应该如何修改？
返回一个长为 $n$ 的 $answer$ 数组，其中 $answer [i]$ 等于删除 $prices [i]$ 后（相当于禁止在第 $i$ 天买卖股票）本题的答案。

欢迎在评论区发表你的思路/代码。

股票买卖系列题目

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

复杂度分析 ​

思考题 ​

股票买卖系列题目 ​

分类题单 ​

复杂度分析

思考题

股票买卖系列题目

分类题单