题解 | #买卖股票的最好时机(一)#

题目主要信息:

• 给出一个数组表示连续多日的股票价格
• 你可以选择在某一天买入股票，在另一天卖出股票，买卖都只有一次机会，不能在同一天
• 假设买卖没有手续费，问最高收益是多少，即卖出的价格减去买入的价格，如果没有利润需要返回0
• 可以看成查找数组中b-a的最大值，其中b必须在a的后面

具体思路:

如果我们在某一天卖出了股票，那么要想收益最高，一定是它前面价格最低的那天买入的股票才可以。因此我们可以利用贪心思想解决，每次都将每日收入与最低价格相减维护最大值。

• step 1：首先排除数组为空的特殊情况。
• step 2：将第一天看成价格最低，后续遍历的时候遇到价格更低则更新价格最低，每次都比较最大收益与当日价格减去价格最低的值，选取最大值作为最大收益。

可以参考以下图示：

代码实现:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0; //维护最大收益
        if(prices.size() == 0) //排除特殊情况
            return res;
        int Min = prices[0]; //维护最低股票价格
        for(int i = 1; i < prices.size(); i++){ //遍历后续股票价格
            Min = min(Min, prices[i]); //如果当日价格更低则更新最低价格
            res = max(res, prices[i] - Min); //维护最大值
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一次遍历数组
• 空间复杂度：$O(1)O(1)$，常数级变量，无额外辅助空间