实时 Top-K 盈利日榜单
Top K PnL Days So Far
开始编码每天收盘后,风控与策略组都要看一张「截至今天的 Top-K 盈利日」榜单——把策略上线以来每个交易日的 PnL(profit and loss,当天净盈亏)按金额从大到小排出前 K 名。这张榜并不是只在最后看一眼,而是每过完一天就要刷新一次:监控面板上滚动展示「截至 D1 的 Top-3」「截至 D2 的 Top-3」...... 一路到今天。研究员盯这张榜是为了快速识别本月有没有出现异常巨大的单日盈利(可能是真 alpha,也可能是数据 bug 或风控失效);运营层面则用 Top-K 的总和给收益分布画一个粗略的尾部画像。
请实现 solution(daily_pnl: list[float], k: int) -> list[list[float]]。daily_pnl 是按时间顺序到达的每日 PnL 序列,k 是榜单大小。返回一个等长的 list[list[float]]:result[i] 是看完 daily_pnl[0..i](含第 i 天)之后的 Top-K 值,按降序排列。注意两条:
- 不足 K 天时不填充。若到第 i 步累计只观察到 i + 1 < K 天,
result[i]就是这 i + 1 个值的降序排列,长度严格等于 i + 1;不要用0、-inf或None把它垫到长度 K。 - 重复值都计入榜单。若
daily_pnl = [3.0, 3.0]、k = 2,那么result[1] = [3.0, 3.0]——两个 3.0 各自占一个位置,并不会因为「值相同」就只算一个。
举例:solution([5.0, 2.0, -1.0, 8.0, 3.0], 3) 应返回 [[5.0], [5.0, 2.0], [5.0, 2.0, -1.0], [8.0, 5.0, 2.0], [8.0, 5.0, 3.0]]。前两步因为还不足 3 天,分别返回长度 1 和 2 的降序前缀;第 3 步刚好 3 天,全员上榜;第 4 天的 8.0 是新高,挤掉之前榜末的 -1.0;第 5 天的 3.0 大于此时榜末的 2.0,把 2.0 替换出榜。
朴素做法是每来一条 PnL 就 sorted(history, reverse=True)[:k],单步 O(n log n)、n 步累计 O(n² log n),在 n = 10⁴ 数据规模下大概会跑成约 10⁹ 量级的比较——超时。正确做法是维护一个大小至多为 K 的最小堆作为 Top-K 候选窗:堆顶始终是当前 Top-K 中最小的那个。新来的 x,若堆没满直接 push;若堆已满则只在 x > 堆顶时执行 heappushpop 替换堆顶。单步 O(log k),n 步总计 O(n log k)。每一步把当前堆排序成降序追加到结果即可——这一步是 O(k log k),因为 K 远小于 n,整体仍然非常快。这就是为什么本题被放进「堆 / Top-K」技术簇:当 K ≪ n 且需要每一步都输出当前 Top-K 时,固定大小的堆是把单步成本与 n 解耦的标准结构。
约束条件
- 0 ≤ len(daily_pnl) ≤ 10000
- 1 ≤ k ≤ 100
- 每个 daily_pnl[i] 是 float,可以为正、零或负(亏损日)
- 返回 list[list[float]],外层长度等于 len(daily_pnl);内层第 i 个列表是看到 daily_pnl[0..i] 后的 Top-K 值,按**降序**排列
- 在第 i 步若已观察到的天数不足 K,返回当前所有已观察值的降序排列(长度等于 i + 1,**不要**用 0 / -inf 之类填充到长度 K)
- Top-K 含义是「值最大的 K 个」;若有重复值,重复值都计入榜单(例如 `daily_pnl=[3.0, 3.0]`、`k=2` → 第二步返回 `[3.0, 3.0]`)
- 时间复杂度需 O(n · (log k + k log k));O(n² log n) 的全排序解在大用例下会超时
样例
Case 1 · example from statement (k=3, mix of warm-up + replacement)
输入: [[5,2,-1,8,3],3]
期望: [[5],[5,2],[5,2,-1],[8,5,2],[8,5,3]]
前两步不足 3 天,分别返回长度 1 和 2 的降序前缀;第 3 步刚好凑齐 3 天,全员上榜。第 4 天的 8.0 是新高,挤掉榜末的 -1.0。第 5 天的 3.0 大于此时榜末的 2.0,把 2.0 替换出榜。注意第 1、2 步**不**用 0 或 -inf 把长度填到 3——长度严格等于已观察的天数。
Case 2 · duplicate values each occupy a slot (k=2)
输入: [[3,3,3],2]
期望: [[3],[3,3],[3,3]]
重复值并不会被 dedup——两个 3.0 各自占榜上一个位置。第 3 天的 3.0 等于堆顶(不是严格更大),所以不入堆,榜单维持 `[3.0, 3.0]`。这个用例考的就是 `>` 与 `>=` 的边界:把替换条件写成 `x >= heap[0]` 仍能拿到正确值(因为值相等),但若再叠上严格的去重逻辑就会错。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · example from statement (k=3, mix of warm-up + replacement)
输入: [[5,2,-1,8,3],3]
期望: [[5],[5,2],[5,2,-1],[8,5,2],[8,5,3]]
前两步不足 3 天,分别返回长度 1 和 2 的降序前缀;第 3 步刚好凑齐 3 天,全员上榜。第 4 天的 8.0 是新高,挤掉榜末的 -1.0。第 5 天的 3.0 大于此时榜末的 2.0,把 2.0 替换出榜。注意第 1、2 步**不**用 0 或 -inf 把长度填到 3——长度严格等于已观察的天数。
Case 2 · duplicate values each occupy a slot (k=2)
输入: [[3,3,3],2]
期望: [[3],[3,3],[3,3]]
重复值并不会被 dedup——两个 3.0 各自占榜上一个位置。第 3 天的 3.0 等于堆顶(不是严格更大),所以不入堆,榜单维持 `[3.0, 3.0]`。这个用例考的就是 `>` 与 `>=` 的边界:把替换条件写成 `x >= heap[0]` 仍能拿到正确值(因为值相等),但若再叠上严格的去重逻辑就会错。