题目链接

https://www.nowcoder.com/practice/61ad3cbe0e7d4db9b64fc2b7b503dfd8

题目描述

给定未来 天的股票价格。每天最多操作一次（买入1股、卖出1股或不操作）。初始时无股票，最终也必须清空股票。求最大收益。

解题思路

这是一个经典的可以通过“后悔贪心”思想解决的问题。核心在于，当我们决定在某天卖出时，我们应该匹配历史上哪一天的买入价格？显然是最低的那个。但这个决策可能不是全局最优的，因为未来可能有更高的卖出价。

“后悔贪心”算法通过优先队列（小顶堆）巧妙地解决了这个问题。

算法思想：

  1. 我们按天数顺序遍历每日股价。
  2. 我们维护一个小顶堆 pq，它存储了所有我们遇到的、可以作为“买入点”的价格。
  3. 当我们遍历到第 天，股价为 时：
    • 我们查看一下 pq 中是否有比 更低的价格。pq 的堆顶 min_price 就是历史最低买入价。
    • 如果 p > min_price：
      • 这表示我们发现了一个盈利机会：在 min_price 那天买入，今天以 p 卖出。
      • 我们应该立刻“锁定”这部分利润，将 p - min_price 累加到总收益中。
      • 后悔机制：为了不错过未来可能出现的更高卖点，我们执行一个“后悔”操作。我们将 min_price 从堆中弹出，然后把当前价格 p 压入堆中。这个操作的精妙之处在于：
        • 它相当于我们完成了 min_price p 的交易。
        • 同时，它虚构了一个新的买入机会，即在今天以价格 p 买入。如果未来某天的价格 p_future > p，我们又可以进行一笔 p p_future 的交易。这两笔交易的总利润为 (p - min_price) + (p_future - p) = p_future - min_price，这恰好等价于我们当初持有 min_price 的股票直到 p_future 时才卖出的总利润。这个机制保证了每一个历史最低买点都能与未来最高的卖点匹配，从而实现全局最优。
    • 无论是否发生交易，我们都需要将当前价格 p 压入小顶堆。这代表在第 天，我们都新增了一个以价格 p 买入股票的机会。

合并操作： 上述逻辑可以合并简化为：

  1. 遍历每日股价 p。
  2. 将 p 压入小顶堆 pq。
  3. 如果堆顶 min_price < p，说明用当前价 p 卖出堆顶的股票可以获利。
  4. 于是，弹出 min_price，累加利润 p - min_price，再将 p 压回堆中（完成后悔操作）。

代码

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> prices(n);
    for (int i = 0; i < n; ++i) {
        cin >> prices[i];
    }

    priority_queue<int, vector<int>, greater<int>> pq; // 小顶堆
    long long total_profit = 0;

    for (int p : prices) {
        // 首先，将当前价格视为一个潜在的买入点
        pq.push(p);

        // 如果堆顶（历史最低买价）低于当前价格，则存在套利空间
        if (pq.top() < p) {
            // 锁定利润
            total_profit += p - pq.top();
            // 弹出已用于交易的最低买价
            pq.pop();
            // “后悔”操作：将当前卖出价作为新的潜在买入点放回
            // 这样，如果未来有更高的价格，可以基于当前价格继续交易
            pq.push(p);
        }
    }

    cout << total_profit << endl;

    return 0;
}

import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] prices = new int[n];
        for (int i = 0; i < n; i++) {
            prices[i] = sc.nextInt();
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 小顶堆
        long totalProfit = 0;

        for (int p : prices) {
            pq.add(p);
            
            if (pq.peek() < p) {
                totalProfit += p - pq.peek();
                pq.poll();
                pq.add(p);
            }
        }
        System.out.println(totalProfit);
    }
}

import heapq

def main():
    n = int(input())
    prices = list(map(int, input().split()))

    pq = []  # 小顶堆
    total_profit = 0

    for p in prices:
        heapq.heappush(pq, p)

        if pq[0] < p:
            profit = p - pq[0]
            total_profit += profit
            heapq.heappop(pq)
            heapq.heappush(pq, p)
            
    print(total_profit)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：贪心算法 + 优先队列（小顶堆）
  • 时间复杂度：，其中 是天数。我们需要遍历 天，每天对优先队列进行最多两次操作（一次push，一次pop），每次操作的复杂度是 ，其中 是堆的大小（）。
  • 空间复杂度：，优先队列在最坏情况下可能需要存储所有 个价格。