【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)。