【Hot 100 刷题计划】 LeetCode 121. 买卖股票的最佳时机 | C++ 贪心/动态规划题解

LeetCode 121. 买卖股票的最佳时机 | C++ 贪心/动态规划一次遍历题解

📌 题目描述

题目级别：简单

给定一个数组prices，它的第i个元素prices[i]表示一支给定股票第i天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

💡 解题思路：贪心算法 / 动态规划 (一次遍历)

最暴力的解法是使用两层for循环，枚举每一天的买入和卖出情况，但这样时间复杂度会达到O(N2)O(N^2)O(N2)，在数据量大的时候必然会超时。

我们需要寻找一种O(N)O(N)O(N)的解法，即只遍历数组一次。
想象一下我们正在看股票走势图，想要获得最大利润，我们其实只需要做两件事：

1. 寻找历史最低点：在遍历每一天价格的时候，我们要记住今天及今天以前，股票出现的最低价格。
2. 计算如果今天卖出的利润：假设我们就是在这个历史最低点买入的，那么如果今天卖出，利润是多少？我们用这个利润去不断刷新我们的“最大利润记录”。

通过这种方式，我们边走边记录“历史最低买入价”，同时边走边结算“当前最大利润”，只需要一次遍历就能得到最优解。

💻 C++ 代码实现

classSolution{public:intmaxProfit(vector<int>&prices){// 记录历史最低价格，初始值为第一天的价格intmi=prices[0];// 记录全局最大利润，初始为 0（因为就算亏本我们也可以选择不买卖）intres=0;// 遍历这支股票每一天的价格for(inti=0;i<prices.size();i++){// 1. 更新历史最低价格mi=min(mi,prices[i]);// 2. 计算如果今天卖出能赚多少钱，并刷新全局最大利润res=max(res,prices[i]-mi);}returnres;}};