一、题目描述

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多只能持有一股股票。你也可以先购买，然后在同一天出售。最后要求返回你能获得的最大利润。

作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2zsx1/

示例1

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 – 1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 – 3 = 3 。总利润为 4 + 3 = 7

示例2

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 – 1 = 4 。总利润为 4 。

示例3

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

数据规模

1 <= prices.length <= 3 * 104

0 <= prices[i] <= 104

二、解题思路

我们以下图为例来示意股票的涨跌情况：

（1）贪心算法

基本思想

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

通过上图可以发现：当股价持续上涨时，只要不出手手中的股票，等到股价上涨到峰值（拐点）再去抛售股票，此时可以获得该股票上涨区域内的最大利润，后面的情况同理。

这是一种典型的贪心思想，即每次通过获得局部最优解来达到整体最优解。如果股票下跌就不用计算，最终只需要把所有股票上涨的时间段内的利润累加就是我们所要求的结果。

公式法理解：如上图a~d之间股价一直是上涨的，所以a天买入等到d天时候卖出，则此时可以获得的最大利润为(d-a)，这个式子也可以写成（b-a)+(c-b)+(d-c)，即每一个上涨区间的差值累加等于上涨总区间的差值。

解题代码

class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length<2){
            return 0;
        }
        int sum=0,index=0,length=prices.length;
        while(index<length){
            //如果股价一直下跌就一直找，直到找到股价开始上涨的点为止
            while(index<length-1&&prices[index]>=prices[index+1])
                index++;
            //当上面的循环结束，此时index位于股价开始上涨的位置处，即这段时间上涨的最小值
            int min=prices[index];//记录此时上涨区间内股价的最小值
            //从最小值位置开始，直到找到股价上涨的最大值为止
            while(index<length-1&&prices[index]<=prices[index+1]){
                index++;
            }
            //计算这段上涨区间的差值，然后累加即为该段上涨区间内的最大利润
            sum+=prices[index++]-min;//结束该段上涨区间的计算，index+1继续循环执行下一轮
        }
        return sum;

    }
}

执行结果

（2）双指针法

基本思想

双指针法又称为滑动窗口法，通过设置左右两个指针，指针间距根据具体情况而定，从而形成了类似于一个方形“滑块”从数组的左边向右滑动，每次判断右指针与左指针所对应的记录值进行比较。

解题代码

class Solution {
    public int maxProfit(int[] prices) {
       int left=0,length=prices.length,sum=0;
        for(int right=1;right<length;right++){
            if(prices[left]<=prices[right]){
                sum+=prices[right]-prices[left];
            }
            left++;//左指针右移

        }
        return sum;
    }
}

执行结果

(3)巧解法

看破这道题本质的一位码友说了八个字：求上升区间高度和言简意赅，一语道破！

解题代码

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n <= 1) return 0;
        int d=0,sum = 0;
        for (int i = 1; i < n; i++) {
            //求相邻元素的差值
            d = prices[i] - prices[i-1];
            //如果差值为正数表面股价上涨，否则为下跌，只需累加上涨区间的差值
            if (d > 0) sum += d;
        }
        return sum;
    }
}