买卖股票的最佳时机

WangScaler: 一个用心创作的作者。

声明：才疏学浅，如有错误，恳请指正。

题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

初次分析

这个题的获取利润的本质就是低价买入，高价卖出。当买入之后，没有价格比当前买入的价格高，则返回0表示未卖出，利润为0。

如果我们把每一天看作要买入的时间，那么后边的那些天就是卖出的日期，每一天都有个最佳的收益。记录这个值，那么所有天的最佳受益值就是我们的答案。

 public int maxProfit(int[] prices) {
        int max = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) {
                int result = prices[j] - prices[i];
                if (result > max) {
                    max = profit;
                }
            }
        }
        return max;
    }

继续分析

两层for循环必不是最佳结果。那么换个角度。我们可以看出，要实现利益最大化，也就是说我们在数组中价格最低时买入，在价格最高时卖出即可，再一个就是控制价格最高的应该在价格最低的后边，否则也不算数。

也就是

• 如【5，4，1，4，5，6】我们在数组中找到最低价1的时候买入，然后开始计算后边的利润【3，4，5】。遍历完利润最大的值就是答案5。
• 如【5，4，3，4，6，1，2，3】开始我们找到一个低价3，比较了两次之后的利润【1，3】最大值3，又遇到一个最低价1，我们则选择买入1，以1重新计算利润【1，2】均不大于3.所以答案为3。

答案

public int maxProfit(int prices[]) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else if (prices[i] - min > max) {
                max = prices[i] - min;
            }
        }
        return max;
    }

复杂度

• 时间复杂度: O(n)，我们只遍历了一次，遍历一遍数组即可，所以时间复杂度为O(n)。
• 空间复杂度：O(1),需要两个常数变量记录最大最小值。

总结

可能有个疑问就是如【5，4，3，4，6，1，2，3】后边遇到更小的数1，相当于重新购买，会不会有一种情况从第一个最小值3-最后的利润要比从第二个最小值到最后的利润值高或者比第一个最小值3-6的利润值高。

答案是肯定不会有这种情况。为什么呢？因为第二个最小数比第一个最小数小，才会重新购买。那么后边出现的数与小数做差肯定不会比上一个最小数大。这个问题的本质就是A-1会小于A-2吗？

这个题本质就是分两步，第一步就是找到最低价即买入时机。找到买入时机之后则是对比利润找到卖出时机。解决这两步，答案就出来了。

都来了，点个赞再走呗！

关注WangScaler，祝你升职、加薪、不提桶！