九章算法 | Amazon 面试题：买卖股票的最佳时机

假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

在线评测地址：LintCode 领扣

样例1

输入: [3, 2, 3, 1, 2]
输出: 1
说明：你可以在第三天买入，第四天卖出，利润是 2 - 1 = 1 

样例2

输入: [1, 2, 3, 4, 5]
输出: 4 
说明：你可以在第0天买入，第四天卖出，利润是 5 - 1 = 4 

样例3

输入: [5, 4, 3, 2, 1]
输出: 0
说明：你可以不进行任何操作然后也得不到任何利润 

算法：贪心

很容易想到的贪心算法。对于每一天的价格，我考虑在那天之前的最低价买入，看看是不是能跟新答案。

• 我们利用一个单元去保存前缀最小值，或者后缀最大值。以下以前缀最小值 low 为例。
• 若当前的 prices[i]−low能更新答案，则更新
• low=min(prices[i],low) ，继续跟新最小值即可。

复杂度分析

• 时间复杂度O(n)
  • 扫描整个数组即可
• 空间复杂度O(1)
  • 常数空间

代码

public class Solution {

    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */

    public int maxProfit(int[] prices) {
        // write your code here

        if (prices == null || prices.length == 0) {
            return 0;
        }
        int minPrice = Integer.MAX_VALUE;  //just remember the smallest price
        int maximumProfit = 0;

        for (int i : prices) {
            minPrice = i < minPrice ? i : minPrice;
            maximumProfit = (i - minPrice) > maximumProfit ? i - minPrice : maximumProfit;

        }
        return maximumProfit;
    }
}

更多题解参考：九章算法