大廠面試真題詳解：買賣股票的最佳時機

假設有一個數組，它的第i個元素是一支給定的股票在第i天的價格。如果你最多隻允許完成一次交易(例如,一次買賣股票),設計一個算法來找出最大利潤。

線上評測位址：

領扣題庫官網 樣例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;
    }
}           

更多題解參考：

九章官網solution