刷题日期：下午9:08 2021年5月26日星期三

个人刷题记录，代码收集，来源皆为leetcode

经过多方讨论和请教，现在打算往Java方向发力

主要答题语言为Java

题目：

剑指 Offer 63. 股票的最大利润

难度中等121

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

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

0 <= 数组长度 <= 10^5

题目分析

一看限制人就傻了，断了两层遍历的暴力念头。

示例一的解释也云里雾里的，难道不应该是先买入再卖出吗。

从前往后遍历，首先找有没有递增的，有的话把最小的设为买，往后找，不断更新最大的卖点，如果出现了最小的卖点也可以记录，然后取最值。

最大最小还有先后的限制，估计还得整一个数组之类的，因为可能有好几对。

初始解答：

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        int in = prices[0], out = prices[0]; //买入和卖出的价格，都初始化最低
        for (int i = 0; i < prices.length - 1; i++) {
            //如果递减则不做事
            if (prices[i] < prices[i + 1] && prices[i] != 0) {
                if (prices[i] < in) {
                    in = prices[i];
                }
                out = prices[i + 1];
            }
            if (prices[i] < prices[i + 1] && prices[i] > out) out = prices[i];
        }
        return out - in;
    }
}

执行结果：解答错误

显示详情 添加备注

输入：[2,1,2,1,0,1,2]

输出：1

预期结果：2

我就醉了，前面的0已经判断为闭市不交易了，和着现在，0成了免费送了呗，这啥股市啊，你家开的。

思路还差一点，不过方向是对的，对怎么维护最大利益想的还不够清楚，方法一也采用了类似的做法，稍加修改就好了

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) return 0;
        int in = prices[0], res = 0; //买入的价格初始化
        for (int i = 1; i < prices.length; i++) {
            //如果递减则不做事
            if (prices[i] <= in) {
                in = prices[i];
            } else {
                res = Math.max(res, prices[i] - in);
            }
        }
        return res;
    }
}

执行结果：通过

显示详情 添加备注

执行用时：1 ms, 在所有 Java 提交中击败了98.16%的用户

内存消耗：37.9 MB, 在所有 Java 提交中击败了94.30%的用户

再学习K神的做法，采用动态规划

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;
    }
}

效果差不多， 执行结果：通过

显示详情 添加备注

执行用时：2 ms, 在所有 Java 提交中击败了66.62%的用户

内存消耗：38.2 MB, 在所有 Java 提交中击败了59.95%的用户

学习他人：

方法一:

mata川L5 2020-02-13 在遍历数组的过程中，维护一个最小值，最小值初试为prices[0]

1. 如果prices[i]大于min，则去更新一下利润res
2. 否则说明当前的prices[i]比min还小，则更新min

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1) {
            return 0;
        }
        int res = 0, min = prices[0];
        for(int i = 1; i < prices.length; i++) {
            if(prices[i] <= min) {
                min = prices[i];
            }else {
                res = Math.max(res, prices[i] - min);
            }
        }
        return res;
    }
}

方法二：

wydxryL1 2021-04-11

执行结果： 通过 显示详情 执行用时： 2 ms , 在所有 Java 提交中击败了 66.06% 的用户 内存消耗： 38.3 MB , 在所有 Java 提交中击败了 52.70% 的用户

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0) return 0;
        int minp=prices[0],maxp=0;
        for(int i=1;i<prices.length;i++){
            minp=Math.min(minp,prices[i]);
            maxp=Math.max(maxp,prices[i]-minp);
        }
        return maxp;
    }
}

方法三：

无敌挂科男L1 4 天前

class Solution {
    public int maxProfit(int[] prices) {
        //在某天卖出的最大利润依赖于之前的最小价格
        //1.遍历一遍，同时更新最低买入价格
        if(prices.length < 2)
            return 0;
        int maxProfit = Integer.MIN_VALUE;
        int minPrice = prices[0];
        for(int i = 1; i < prices.length; ++i){
            //更新最大收益
            maxProfit = Math.max(prices[i] - minPrice, maxProfit);
            //更新最低买入价格
            minPrice = Math.min(prices[i], minPrice);
        }
        return maxProfit > 0 ? maxProfit : 0;
    }
}

方法四：

K神 暴力法的时间复杂度为 O(n^2)。考虑使用动态规划降低时间复杂度，以下按照流程解题。

作者：jyd
链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/solution/mian-shi-ti-63-gu-piao-de-zui-da-li-run-dong-tai-2/
来源：力扣（LeetCode）

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;
    }
}

总结

以上就是本题的内容和学习过程了，重点在于如何更新最低价和最高价，或者聪明点学K神直接更新最大利润，能想出来递推公式是关键。

欢迎讨论，共同进步。

原文链接:https://blog.csdn.net/qq_39295220/article/details/117306414