题解 | #低买高卖#

题目链接

BISHI51 低买高卖

题目描述

给定预测的天数 $n$ 和股票第 $i$ 天的收盘价 $p_i$ ，每天最多可操作一次，每次可以买入或卖出一股，或不操作。初始时无持仓，且不能做空；第 $n$ 天收盘时必须清空所有持仓。请设计买卖策略，使得最终获得收益最大，并输出该最大收益。

解题思路

我们使用“反悔贪心”策略：维护一个最小堆来存储已买入的股价。遍历每一天的股价 $p_i$ ：

将 $p_i$ 入堆。
若堆顶价格小于当前价格 $p_i$ ，说明可以用最低买入价“反悔”并在当前价卖出一股，获得收益 $p_i - ext{heap.top()}$ ：
- 弹出堆顶，累加收益 $p_i - ext{pop ext{前的堆顶}}$
- 再将 $p_i$ 入堆，保持与之后交易的衔接。最终堆中元素会对应未被卖出的买入记录，变量 profit 为最大收益。该算法时间复杂度为 $\mathcal{O}(n\log n)$ ，空间复杂度为 $\mathcal{O}(n)$ 。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n;
    cin >> n;
    vector<ll> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    priority_queue<ll, vector<ll>, greater<ll>> minHeap;
    ll profit = 0;
    for (int i = 0; i < n; ++i) {
        minHeap.push(p[i]);
        if (minHeap.top() < p[i]) {
            ll buy = minHeap.top();
            minHeap.pop();
            profit += p[i] - buy;
            minHeap.push(p[i]);
        }
    }
    cout << profit << '\n';
    return 0;
}

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] p = new long[n];
        for (int i = 0; i < n; ++i) {
            p[i] = sc.nextLong();
        }
        PriorityQueue<Long> minHeap = new PriorityQueue<>();
        long profit = 0;
        for (int i = 0; i < n; ++i) {
            minHeap.add(p[i]);
            if (minHeap.peek() < p[i]) {
                long buy = minHeap.poll();
                profit += p[i] - buy;
                minHeap.add(p[i]);
            }
        }
        System.out.println(profit);
    }
}

def main():
    n = int(input())
    p = list(map(int, input().split()))
    import heapq
    min_heap = []
    profit = 0
    for price in p:
        heapq.heappush(min_heap, price)
        if min_heap[0] < price:
            buy = heapq.heappop(min_heap)
            profit += price - buy
            heapq.heappush(min_heap, price)
    print(profit)

if __name__ == '__main__':
    main()

算法及复杂度

算法：线性扫描“下降-上升”区间并贪心匹配，时间复杂度为 $\mathcal{O}(n)$ 。
时间复杂度： $\mathcal{O}(n)$ 。
空间复杂度： $\mathcal{O}(1)$ 。