?个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
??如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪
题目描述
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖 一次 该股票可能获得的利润是多少？
例如一只股票在某些时间节点的价格为 [9,11,8,5,7,12,16,14]。
如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大的利润 11。
数据范围
输入数组长度 [0,500]。
样例
输入：[9, 11, 8, 5, 7, 12, 16, 14] 输出：11
方法一：一次遍历 O(n)
这道题我们可以用一个变量 minv 来记录数组中最小值，然后在遍历的过程中不断更新。因为题意是需要输出最大利润，所以我们需要使买入股票的价格尽可能的小，并且卖出股票的价格尽可能大，拿题目的样例进行举例，假设有数组 [9, 11, 8, 5, 7, 12, 16, 14] 。
第一步： 初始化 minv 为第一个数 9 ，且 ans = 0 。
第二步： 计算差值 11 - 9 > ans = 0 ，故更新 ans = 2 ，且 11 > 9 ，所以 minv 不用更新。
第三步： 计算差值 8 - 9 < ans = 2 ，故不用更新 ans ，且 8 < 9 ，所以更新 minv = 8 。
第四步： 计算差值 5 - 8 < ans = 2 ，故不用更新 ans ，且 5 < 8 ，所以更新 minv = 5 。
第五步： 计算差值 7 - 5 = ans = 2 ，故不用更新 ans ，且 7 > 5 ，所以 minv 不用更新。
第六步： 计算差值 12 - 5 > ans = 2 ，故更新 ans = 7 ，且 12 > 5 ，所以 minv 不用更新。
第七步： 计算差值 16 - 5 > ans = 7 ，故更新 ans = 11 ，且 16 > 5 ，所以 minv 不用更新。
第八步： 计算差值 14 - 5 < ans = 11 ，故不用更新 ans ，且 14 > 5 ，所以 minv 不用更新。此时已经遍历到最后一个值，故直接返回结果 ans = 11 。
class Solution {
public:
int maxDiff(vector<int>& nums) {
if (nums.empty()) return 0;
int minv = nums[0], ans = 0;
for (int i = 1; i < nums.size(); i++)
{
ans = max(ans, nums[i] - minv);
minv = min(minv, nums[i]);
}
return ans;
}
};
欢迎大家在评论区交流~