← 返回编程题库
coding-subarray-min-cost-fill中等免费版2000ms未尝试

订单簿全档位区间的均匀打穿股数总量

Total Uniform-Fill Shares across Every Order-Book Level Range

开始编码

实现 solution(depths: list[int]) -> int。输入 depths 是订单簿一侧按价格档位顺序排列的可成交深度(每档可成交股数)。对任意连续档位区间 depths[l..r]0 <= l <= r < N),定义它的均匀打穿股数(r - l + 1) * min(depths[l..r])——区间宽度乘上区间瓶颈深度。这相当于:从该区间的每一档都恰好取走瓶颈深度那么多股,整段就是一次受瓶颈卡死的均匀打穿。返回所有 N*(N+1)/2 段连续档位区间的均匀打穿股数之和(一个整数)。

solution([4, 2, 6, 3, 5]) 返回 87。共 15 段连续档位区间,按长度分组列出 宽度 * 瓶颈

  • 长度 1:1*4 + 1*2 + 1*6 + 1*3 + 1*5 = 20
  • 长度 2:2*min(4,2) + 2*min(2,6) + 2*min(6,3) + 2*min(3,5) = 4 + 4 + 6 + 6 = 20
  • 长度 3:3*min(4,2,6) + 3*min(2,6,3) + 3*min(6,3,5) = 6 + 6 + 9 = 21
  • 长度 4:4*min(4,2,6,3) + 4*min(2,6,3,5) = 8 + 8 = 16
  • 长度 5:5*min(4,2,6,3,5) = 10

合计 20 + 20 + 21 + 16 + 10 = 87。

空 ladder 返回 0;长度为 1 的 ladder 返回唯一的那个元素;长度 N、所有档位深度都为 d 的 ladder 返回 d * N * (N+1) * (N+2) / 6

实现细节由 stubs/stub.py 提供。

实践背景

做盘前流动性评分的研究员在扫订单簿深度 ladder 时反复问的一个问题是:“对这一段连续档位,如果被强行做一次 *均匀* 打穿——每一档都取相同股数、且不超过最薄那档的容量——能取走多少股?”答案就是 宽度 * 瓶颈深度,因为这次均匀打穿被卡在最薄那档的容量。把它对所有连续档位区间求和,得到的标量同时反映了交易员关心的两件事:更深的档位让单段贡献变大,连续多档同深度的长跑会让贡献超线性放大(因为它会出现在大量相互重叠的区间里)。算法上的关键是把每档的边际贡献写成 depths[i] * L * R * (L + R) / 2,其中 L 是它到左侧最近严格更薄档位的距离,R 是它到右侧最近不更厚档位的距离——这种不对称的并列拆分是避免相邻同深度档位被重复计数的唯一稳妥方式。宽度加权让严格/非严格的选择尤其要紧:错误归属一个并列区间不再是 1 的偏差,而是整段宽度的偏差。

约束条件

  • 0 <= len(depths) <= 50000
  • 每个 depths[i] 为满足 0 <= depths[i] <= 1_000_000_000 的整数(允许 0,对应该档位为空)
  • 输出为所有连续下标区间 (区间宽度 * 区间瓶颈深度) 之和的精确整数,比对器使用整数精确匹配
  • 空 ladder 返回 0;长度为 1 的 ladder 返回 depths[0](仅一个长度为 1 的区间,宽度 1,瓶颈 depths[0])
  • depths 中存在并列时不可重复计数——任何在多个相等位置同时取到最小值的区间,必须只由其中一个位置‘负责’

样例

Case 1 · statement-example: depths=[4,2,6,3,5] uniform-fill sum is 87

输入: [[4,2,6,3,5]]

期望: 87

5 个档位共 15 个连续区间。逐区间 width*bottleneck:长度1贡献 1*(4+2+6+3+5)=20;长度2贡献 2*(2+2+3+3)=20;长度3贡献 3*(2+2+3)=21;长度4贡献 4*(2+2)=16;长度5贡献 5*2=10。合计 87。

Case 2 · visible: depths=[7,1,5,1,3,1] tie spread test

输入: [[7,1,5,1,3,1]]

期望: 68

三个相等的最小档位(深度 1)出现在不同位置;宽度加权下,并列归属错误会偏差整段宽度,因此非对称比较至关重要。期望 68。

Case 3 · visible: all-equal depths=[2,2,2,2] uniform-fill sum is 40

输入: [[2,2,2,2]]

期望: 40

4 档全部相等(深度 2),共 10 个区间,宽度之和 = 4*1 + 3*2 + 2*3 + 1*4 = 20,乘以瓶颈 2 得 40;测试 ties 下宽度加权与归属一致性。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · statement-example: depths=[4,2,6,3,5] uniform-fill sum is 87

输入: [[4,2,6,3,5]]

期望: 87

5 个档位共 15 个连续区间。逐区间 width*bottleneck:长度1贡献 1*(4+2+6+3+5)=20;长度2贡献 2*(2+2+3+3)=20;长度3贡献 3*(2+2+3)=21;长度4贡献 4*(2+2)=16;长度5贡献 5*2=10。合计 87。

Case 2 · visible: depths=[7,1,5,1,3,1] tie spread test

输入: [[7,1,5,1,3,1]]

期望: 68

三个相等的最小档位(深度 1)出现在不同位置;宽度加权下,并列归属错误会偏差整段宽度,因此非对称比较至关重要。期望 68。

Case 3 · visible: all-equal depths=[2,2,2,2] uniform-fill sum is 40

输入: [[2,2,2,2]]

期望: 40

4 档全部相等(深度 2),共 10 个区间,宽度之和 = 4*1 + 3*2 + 2*3 + 1*4 = 20,乘以瓶颈 2 得 40;测试 ties 下宽度加权与归属一致性。