【剑指offer系列】70. 股票的最大利润

这里是剑指offer系列的延续，作者将利用C++实现继续完成该系列的学习，剑指offer，喜欢的话可以点赞关注＋收藏，加油更新中ing。

---

题目70. 股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖 一次 该股票可能获得的利润是多少？

例如一只股票在某些时间节点的价格为 [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

【题解】— 遍历 & 贪心

由于只允许做一次股票买卖交易，枚举每一天作为卖出的日子，买入日子一定在卖出日子之前，为了获利最多，希望买入的日子的股票价格尽可能低。

用minnum[i]记录第0-i天的最低价格，则在第i天卖出的最大获利为nums[i]-minnum[i]，枚举i找到最大获利。

贪心法：
由于只允许做一次股票买卖交易，枚举每一天作为卖出的日子，买入日子一定在卖出日子之前，为了获利最多，希望买入的日子的股票价格尽可能低。

复杂度分析：

时间复杂度为O(n)。
1

C++代码实现：

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        vector<int>minnum(nums.size(),0);
        minnum[0] = nums[0];
        for(int i = 1; i<nums.size(); i++){
            if(nums[i]<minnum[i-1])
                minnum[i] = nums[i];
            else
                minnum[i] = minnum[i-1];
        }
        int res = 0;
        for(int i = 0;i<nums.size();i++){
            int delta = nums[i] - minnum[i];
            if(delta > res)
                res = delta;
        }
        return res;
    }
};

// 贪心法
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int buy=nums[0],diff=0;
        for(auto &x:nums){
            if(x<buy) buy=x;
            if(x-buy>diff) diff=x-buy;
        }
        return diff;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

剑指offer系列将后续持续更新，有帮助的话，欢迎点赞👍、收藏⭐️＋关注✌️哟~

---