题目

121-买卖股票的最佳时机

给定一个数组 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。

思路

这道题使用双指针法只需遍历数组一次就可以得到最优结果，即利润最大的。

只遍历了一次数组。时间复杂度O(n)

只使用了常数级的变量保存相应的结果。空间复杂度O(1)

解题方法

定义两个指针，一个慢指针，指向数组的0号位置。一个快指针，指向数组的1号位置。遍历数组的过程中实时判断当前慢指针和快指针所指位置的数谁更大。

如果慢指针的数更大，就把慢指针移动到快指针的位置，也就是保证慢指针指向股票价格最低的时候，并且让快指针向后继续走。

如果快指针的数更大，则计算快慢指针所指的数之差，使用中间变量记录这个差值，并且在遍历过程中更新它，最后得到的结果就是利润最大值。

时间复杂度

添加时间复杂度, 示例： O(n)

空间复杂度:

添加空间复杂度, 示例： O(1)

备注：第17行的continue;可加可不加不影响运行成功，但是我加了之后提交时的执行时间只有1ms，而不加为2ms，变大了50%嘞！！

class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        int pre = 0;
        int later = 1;
        while (later < prices.length) {
            if (prices[pre] >= prices[later]) {
                pre = later;
                later++;
            } else {
                int differ = prices[later] - prices[pre];
                if (max < differ) {
                    max = differ;
                    later++;
                } else {
                    later++;
                    continue; //可加可不加
                }
            }
        }
        return max;
    }
}