买卖股票的最佳时机（九）

一、题目描述

这是 LeetCode 热题 HOT 100 上第二十一题：买卖股票的最佳时机，难度为 简单。

Tag：「数组」、「贪心算法」

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入： [7,1,5,3,6,4]
输出： 5
解释： 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入： prices = [7,6,4,3,1]
输出： 0
解释： 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1、1 <= prices.length <= 105

2、0 <= prices[i] <= 104

二、解题思路

1、这道题使用贪心算法能够快速的计算出结果

2、贪心算法是指：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。

那么这道题使用贪心算法：只要是上涨的我们就要计算他们的差值进行累加，不需要再找开始上涨的最小值和最大值。为什么能这样计算，我举个例子。

比如 a<b<c<d，因为从 a 到 d 一直是上涨的，那么最大值和最小值的差值就是 d-a，也可以写成(b-a)+(c-b)+(d-c)，搞懂了这个公式所有的一切都明白了。如果还不明白，可以想象成数组中前一个值减去后一个值，构成一个新的数组，我们只需要计算这个新数组中正数的和即可，如下图：

这里只需要计算新数组中正数的和，也就是4+3=7

代码实现：

public int maxProfit(int[] prices) {
    int total = 0;
    for (int i = 0; i < prices.length - 1; i++) {
        //原数组中如果后一个减去前一个是正数，说明是上涨的，
        //我们就要累加，否则就不累加
        total += Math.max(prices[i + 1] - prices[i], 0);
    }
    return total;
}

时间复杂度和空间复杂度分析：

时间复杂度：O(n)，n 表示 prices 的长度，最多执行 n-1 次，去掉常数项，最终时间复杂度为：O(n)

空间复杂度：O(1)，这里我们仅使用到常数个变量

三、总结

本道算法题难度为简单，我们使用贪心算法快速的得到了答案

好了，本篇文章到这里就结束了，感谢你的阅读🤝