剑指offer 71. 股票的最大利润

✍个人博客：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
1
2
3

方法一：一次遍历 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

欢迎大家在评论区交流~