Best Time to Buy and Sell Stock

121. 买卖股票的最佳时机

分析

维护最低价格：
- 用变量 min_price 记录当前遍历过程中的最低股票价格，初始化为 INT_MAX
计算当前利润：
- 对于每一天的价格 price，计算当天卖出时的利润：profit = price - min_price
更新最大利润：
- 用变量 res 记录遍历过程中的最大利润，初始化为 0
动态更新：
- 每遍历一天，更新 min_price 和 res，确保始终找到最优解

时间复杂度

遍历一次数组，每个元素只处理一次，时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        int min_price = INT_MAX;  // 初始化最低价格
        int res = 0;              // 初始化最大利润
        for (int price : prices)
        {
            // 更新最大利润
            res = std::max(res, price - min_price);
            // 更新最低价格
            min_price = std::min(min_price, price);
        }
        return res;  // 返回最大利润
    }
};