【Lintcode】1691. Best Time to Buy and Sell Stock V（配數學證明）

題目位址：

https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-v/description

給定一個數組 A A A，代表每天的股價。每天最多允許做一次交易，也可以不做。問能得到的最大利潤。

思路是最小堆。開一個最小堆，同時周遊 A A A。每天先看一下目前堆頂的股價是否小于當天的股價，如果小，說明有利可圖，則執行交易，并将當天股價入堆兩次；否則隻入堆一次。關于為什麼入堆兩次，是因為後面可能存在更高的股價，如果存在的話，可以把兩次交易捏成一次，這樣可以減少交易次數，進而增加最大利潤的可能性。這個思路本質是貪心的，需要證明。

算法正确性證明：

對天數做數學歸納法。如果 A A A長度為 1 , 2 1,2 1,2則顯然正确。假設 A A A長度為 n n n時正确，當 A A A長度為 n + 1 n+1 n+1時，首先當周遊到 A [ n − 1 ] A[n-1] A[n−1]的時候，由歸納假設，答案裡已經存儲的是能獲得的最大利潤，并且得到了若幹合法交易。當周遊到 A [ n ] A[n] A[n]的時候，我們首先看一下前面 n n n天得到的所有合法交易，此時堆裡存放的，要麼是某次合法交易的賣價，要麼是某天的股票價格。如果堆頂大于等于 A [ n ] A[n] A[n]，那麼以 A [ n ] A[n] A[n]為賣價做交易不會得到更大的利潤（如果不是的話，例如以 A [ j ] A[j] A[j]的價格買入，然後以 A [ n ] A[n] A[n]的價格賣出，這說明 A [ j ] < A [ n ] A[j]<A[n] A[j]<A[n]，但是 A [ j ] A[j] A[j]不在堆裡，說明遇到了更高的賣價，這與最優是以 A [ n ] A[n] A[n]賣沖突了），是以此時得到的最大利潤就是最終的最大利潤，算法正确。如果堆頂小于 A [ n ] A[n] A[n]，那麼分兩種情況考慮。如果堆頂對應的價格的那一天，該價格進堆了兩次，那就将它在if裡進堆的那一次的交易取消，改為在 A [ n ] A[n] A[n]的時候賣，這樣獲得的總利潤就是 A [ n ] A[n] A[n]與堆頂那次交易的買價之差，相當于前 n n n天利潤再加上 A [ n ] A[n] A[n]與堆頂之差；如果隻進堆一次，那說明那一天可以買，然後再以 A [ n ] A[n] A[n]的價格賣出，則總利潤是前 n n n天利潤再加上 A [ n ] A[n] A[n]與堆頂之差。由于堆頂是堆内的最小值，是以以堆頂作為買入價或者“過渡價”，再以 A [ n ] A[n] A[n]作為賣出價獲得的利潤是最高的。綜上，算法正确。

代碼如下：

import java.util.PriorityQueue;

public class Solution {
    /**
     * @param a: the array a
     * @return: return the maximum profit
     */
    public int getAns(int[] a) {
        // write your code here
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int res = 0;
        for (int price : a) {
            // 如果今天價格比之前遇到過的最低價高，就計入新增收益
            if (minHeap.size() > 0 && price > minHeap.peek()) {
                res += price - minHeap.poll();
                // 仍然需要将今天價格入堆
                minHeap.offer(price);
            }
            
            // 将今天價格入堆
            minHeap.offer(price);
        }
        
        return res;
    }
}
           

時間複雜度 O ( n log ⁡ n ) O(n\log n) O(nlogn)，空間 O ( n ) O(n) O(n)。