题目描述

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

例如一只股票在某些时间节点的价格为 [9,11,8,5,7,12,16,14]。

如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大的利润 11。

样例

输入：[9, 11, 8, 5, 7, 12, 16, 14]

输出：11

算法1

小根堆

时间复杂度 O(nlogn) ,空间复杂度 O(n)

C++ 代码

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n=nums.size(),ans=0;
        if(n==0||n==1)
            return 0;
        priority_queue<int,vector<int>, greater<int> > pq;
        pq.push(nums[0]);
        for(int i=1;i<n;i++){
            ans=max(ans,nums[i]-pq.top());
            pq.push(nums[i]);
        }
        return ans;
    }
};

算法2

遍历

时间复杂度 O(n), 空间复杂度 O（1）

C++ 代码

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n=nums.size(),ans=0,MIN;
        if(n==0||n==1)
            return 0;
        MIN=nums[0];
        for(int i=1;i<n;i++){
            ans=max(ans,nums[i]-MIN);
            if(nums[i]<MIN)
                MIN=nums[i];
        }
        return ans;
    }
};