75-买卖股票的最好时机

题⽬描述

假设你有⼀个数组 prices ，⻓度为 n ，其中 prices[i] 是股票在第 i 天的价格，请根据这个价格数组，返回买卖股票能获得的最⼤收益

1. 你可以买⼊⼀次股票和卖出⼀次股票，并⾮每天都可以买⼊或卖出⼀次，总共只能买⼊和卖出⼀次，且买⼊必须在卖出的前⾯的某⼀天
2. 如果不能获取到任何利润，请返回 0
3. 假设买⼊卖出均⽆⼿续费

示例1：
输⼊：[8,9,2,5,4,7,1]
返回值: 5
说明: 在第3天(股票价格 = 2)的时候买⼊，在第6天(股票价格 = 7)的时候卖出，最⼤利润 = 7-2 = 5，不能选择在第2天买⼊，第3天卖出，这样就亏损7了；同时，你也不能在买⼊前卖出股票。

示例2：
输⼊：[2,4,1]
返回值: 2

思路及解答

暴⼒穷举

这⾥涉及的节点⽆⾮是买⼊，卖出，那么我们遍历所有的数据，作为买⼊⽇期，同时将该⽇期后⾯每⼀个都作为卖出⽇期来计算，只要维护最⼤的利润即可。

public class Solution63 {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int len = prices.length;
        // 买⼊时间
        for (int i = 0; i < len; i++) {
            // 卖出时间
            for (int j = 0; j < i; j++) {
                // 最⼤的收益
                ans = Math.max(ans, prices[i] - prices[j]);
            }
        }
        return ans;
    }
}

• 时间复杂度： O(n2)
• 空间复杂度：O(1)

贪⼼法

我们要想得到⼀个最⼤的利润，其实就是要两者差值最⼤。如果让差值最⼤，假设在当天卖出，那么什么时候买⼊最好呢？

当然是在前⾯找到最⼩的买⼊点，⽐如：

⽽前⾯的最⼩值，其实我们在遍历的时候是可以不断维护的，所以我们只要遍历⼀次数组即可。

public class Solution63 {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE;
        int result = 0;
        for (int value: prices) {
            // 维护最⼩值
            min = Math.min(min, value);
            // 当前值减去前⾯最⼩值，与利润最⼤值对⽐，维护好利润最⼤值
            result = Math.max(result, value - min);
        }
        return result;
    }
}

时间复杂度为O(n) ,空间复杂度为O(1)

其实还有单调栈的写法，也就是栈顶的元素永远是前⾯遍历的元素⾥⾯最⼩的，这样我们每次都是和栈顶元素相减，这个和上⾯的贪⼼算法其实是⼀样的，只不过上⾯的⽤min 来存储最⼩值，单调栈⽤栈来保存。