2021/1/20 买卖股票的最好时机

题目描述

假设你有一个数组，其中第 i 个元素是股票在第 i 天的价格。
你有一次买入和卖出的机会。（只有买入了股票以后才能卖出）。请你设计一个算法来计算可以获得的最大收益。

示例1

输入

[1,4,2]

返回值

3

示例2

输入

[2,4,1]

返回值

2

解题思路

1. 可知买入操作必定在卖出操作之前，数组可以一直往后推，不需要再回头；
2. 本质是找最小值和最大值，可以使用暴力解法。
3. 因为买入操作在卖出操作之前，前面的值无论如何都要比后来的值小才可以进行计算，所以可以忽略前大后小的情况，可以使用贪心算法，记录最小值以及 当前最小值后面的 最大值。

Java代码实现

// 暴力解法求最大差
public int maxProfit (int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int max = 0;
        for (int i = 0; i < prices.length - 1; ++i) {
            for (int j = i + 1; j < prices.length; ++j) {
                if (prices[j] - prices[i] > max) {
                    max = prices[j] - prices[i];
                }
            }
        }
        return max;
}

// 贪心
public int maxProfit (int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int max = 0;
        int min = prices[0];
        for (int i = 1; i < prices.length; ++i) {
            min = prices[i] < min ? prices[i] : min;
            max = prices[i] - min > max ? prices[i] - min : max;
        }
        return max;
}