【LeetCode】剑指 Offer 63. 股票的最大利润 p304 -- Java Version

题目链接：https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/

1. 题目介绍（63. 股票的最大利润）

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

【测试用例】：

【条件约束】：

【相关题目】：

• 注意：本题与主站 121. 买卖股票的最佳时机 题目相同。

2. 题解

2.1 一次遍历 – O(n) ⭐

时间复杂度O(n)，空间复杂度O(1)

假设给定的数组为：[7, 1, 5, 3, 6, 4]
如果我们在图表上绘制给定数组中的数字，我们将会得到：

【解题思路】：
要想获得最大收益：那么我们一定要在 最低点买入，最高点卖出 才行，同时还存在一个前提：必须先买入，后卖出，这个很好理解，简言之，你还没买呢，拿什么卖呢；所以我们就得到了一个关键信息：假设我们想要在第 i 天卖出股票，那么最低点只可能是 前 i-1天的某一天。
……
想清楚了以上思路，我们就很容易解题了：
我们可以假设 f(i) 为卖出价为数组中第 i 个数字时可能获得的最大利润。显然，在卖出价固定时，买入价越低获得的利润越大。也就是说，如果在扫描到数组中第 i 个数字时，只要我们能够记住之前的 i -1 个数字中的最小值，就能计算出在当前价位卖出时可能得到的最大利润。
……
【实现策略】：

1. 定义变量 min 和 maxProfit，用来记录 第 i 个数字前的最小值，以及当前的最大利润；
2. 遍历数组，逐一判断和更新最小值和最大利润；
3. 遍历结束，判断一下利润是否为正，即存在收益，如果收益为负，则返回0，收益为正，则正常返回。
   

class Solution {
    // Solution1：
    // 我们要找出卖出价为 i 时的最大利润
    // 那么关键点就在于如何找到 前 i-1 个数中的最小值
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0; // 无效输入判断
        int min = prices[0];
        int maxProfit = prices[1] - min;
        for (int i = 2; i < prices.length; i++) { // 遍历数组
            if (prices[i-1] < min) min = prices[i-1]; // 如果后面遍历到的元素小于最小值，那么就替换min
            int currProfit = prices[i] - min; // 那么当前的收益就发生了改变
            maxProfit = Math.max(maxProfit,currProfit); // 保留最大利益
        }
        return maxProfit < 0 ? 0 : maxProfit; // 负收益的情况返回0
    }
}

该题还可以通过动态规划来理解：

状态转移方程：

殊途同归：和一次遍历是一样的，这里也就是学习一下动态规划的思路。

class Solution {
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for(int price : prices) {
            cost = Math.min(cost, price);
            profit = Math.max(profit, price - cost);
        }
        return profit;
    }
}

3. 参考资料

[1] 股票的最大利润 – 力扣官方题解
[2] 面试题63. 股票的最大利润（动态规划，清晰图解）-- Krahets