描述

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

示例1

输入：
[1,4,2]

返回值：
3

示例2

输入：
[2,4,1]

返回值：
2

思路

这个和咱们现实中买股票是一样的，总是希望在最低点买入，在最高点卖出。这道题也是如此，咱们只要找到那天是最低点，并计算每天卖出能挣多少钱，找到卖出最多钱的那天就是这道题的答案。

AC 代码

    public int maxProfit (int[] prices) {
        // write code here
        if (prices == null || prices.length < 1) {
            return -1;
        }
        // 历史最低价格
        int minPrice = Integer.MAX_VALUE;
        // 最大的差价
        int maxProfit = 0;
        // 遍历每天
        for (int i = 0; i < prices.length; i ++) {
            // 如果价格比目前记录的最低价格还低，那么就今天买入！
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else {
                // 否则就计算今天卖出能赚多少钱
                int price = prices[i] - minPrice;
                // 更新赚钱的最大差值
                maxProfit = price > maxProfit ? price : maxProfit;
            }
        }
        return maxProfit;
    }

• 时间复杂度：O(n)，n 数组长度。
• 空间复杂度：O(1)，没有浪费额外空间。

最后

大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。