121.买卖股票的时机

1.一刷

给定一个数组 prices ，它的第 i 个元素 prices[i]表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

输入：[7,1,5,3,6,4] 输出：5

1. 一种思路从后往前遍历，以当前i为买入日子，则最大利润是i右边最大值-prices[i]。
2. 另一种思路从前往后遍历，以当前i为卖出日子，则最大利润是prices[i]-i左边最小值。

2.二刷+双指针

• 左指针作为买入日子

• 右指针

  • 右指针的价格如果大于左指针则继续移动

  • 如果右指针小于左指针的价格，那么更新将左指针买入日子更新为右指针。

    因为如果右指针后面如果出现价格更高的股票，那么显然此时将右指针作为买入日子得到的利润，比将左指针作为买入日子得到的利润更大。

• 右指针移动时，用一个变量maxheight维护【left,right】之间的最大值。

class Solution {
    public int maxProfit(int[] prices) {
        int max=0;
        int left=0,right=0;
        while(right<prices.length){
            int maxheight=prices[left];
            while(right<prices.length&&prices[right]>=prices[left]){
                maxheight=Math.max(maxheight,prices[right]);
                right++;
            }
            max=Math.max(max,maxheight-prices[left]);
            left=right;
        }
        return max;
    }
}