121. 买卖股票的最佳时机

一、题目描述

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

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。

设计一个算法来计算你所能获取的最大利润。

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

二、解题思路

1、找到一个小值，然后从这个小值开始往右查找大值，并更新这期间的最大差值
2、在查找大值的过程中，如果遇到一个更小值，则更新小值的位置，重新进行1步骤

 lp  rp
 ___ ___ ___ ___ ___ ___ ___ 
| 2 | 2 | 3 | 1 | 4 | 5 | 6 |      => maxDiffVal = 2 - 2 = 0

 lp      rp
 ___ ___ ___ ___ ___ ___ ___ 
| 2 | 2 | 3 | 1 | 4 | 5 | 6 |      => maxDiffVal = 3 - 2 = 1

            lp;rp
 ___ ___ ___ ___ ___ ___ ___ 
| 2 | 2 | 3 | 1 | 4 | 5 | 6 |      => maxDiffVal = 1

             lp  rp
 ___ ___ ___ ___ ___ ___ ___ 
| 2 | 2 | 3 | 1 | 4 | 5 | 6 |      => maxDiffVal = 4 - 1 = 3

             lp           rp
 ___ ___ ___ ___ ___ ___ ___ 
| 2 | 2 | 3 | 1 | 4 | 5 | 6 |      => maxDiffVal = 6 - 1 = 5

类似这种效果。

但是，后面的差值就不一定比前面的差值大。

举个例子，把上面的 3 改成 9：

 lp      rp
 ___ ___ ___ ___ ___ ___ ___ 
| 2 | 2 | 9 | 1 | 4 | 5 | 6 |      => maxDiffVal = 9 - 2 = 7

            lp;rp
 ___ ___ ___ ___ ___ ___ ___ 
| 2 | 2 | 9 | 1 | 4 | 5 | 6 |      => maxDiffVal = 7

             lp  rp
 ___ ___ ___ ___ ___ ___ ___ 
| 2 | 2 | 9 | 1 | 4 | 5 | 6 |      => maxDiffVal = 7 > 4 - 1 = 3

             lp           rp
 ___ ___ ___ ___ ___ ___ ___ 
| 2 | 2 | 9 | 1 | 4 | 5 | 6 |      => maxDiffVal = 7 > 6 - 1 = 5

这种情况下，最大值就是之前的差值，所以更新最大差值时需要和之前的比较过才行。

三、复杂度分析

• 时间 O(n)
• 空间 O(1)

四、参考代码

/**
 * 最大收益
 *
 * @param prices 价格数组
 * @return 最大收益
 */
private int maxProfit(int[] prices) {
    int maxDiffVal = 0;
    int lp = 0, n = prices.length;
    for (int rp = lp; rp < n; rp++) {
        if (prices[rp] < prices[lp]) {
            // 找到更小值，那后面的最大差值就和之前的最小值没关系了
            // 后面就用最新的最小值来计算差值
            lp = rp;
        } else if (prices[rp] - prices[lp] > maxDiffVal) {
            // 找到更大值，更新最新的差值
            maxDiffVal = prices[rp] - prices[lp];
        }
    }
    return maxDiffVal;
}