买卖股票的最好时机(一)（贪心）

题意

给一个股票的价格变化值数组，问进行一次购买后再进行一次卖出，问能获取的最大差值是多少

思路分析

以题目样例数据[8,9,2,5,4,7,1]为例

什么时候卖

假设到达某一天时，我已经持有了股票，那么什么时候卖呢？

如图所示，不论我当前持有的股票的买入价格是多少，从今往后，越高的价格对我卖出来说能获得的差值会越大。

什么时候买

虽然实际操作上先买后卖，但从数学上，可以逆着时间考虑。

假设到达某一天时，我卖出了股票，那么这张股票什么时候买能获得最大差值呢？

如图所示，不论我当前卖价是多少，在卖出之前，越低的买价对我卖出来说能获得的差值会越大。

也就是 当前值 减去 之前的最小值

cur - minpre

维护到当前为止的最小值

每次计算后差值后，更新到当前为止的最小值

minpre = min(minpre,cur);

计算最大差值

用一个变量ans记录最大差值，每次计算新的差值后，更新它

ans = max(ans,cur-minpre);

题解

将上面的逻辑联系起来

class Solution {
public:
    /**
     * 
     * @param prices int整型vector 
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        int minpre = 10000; // 之前最小值
        int ans = 0;
        for(auto cur:prices){
            ans=max(ans,cur-minpre);
            minpre = min(minpre,cur);
        }
        return ans;
    }
};

复杂度分析

时间复杂度 : 所有位置计算一次$O(n)O(n)$

空间复杂度 : 常数个临时变量,$O(1)O(1)$