上一次更强买价的距离:到最近一次严格更高买价 print 的间隔
Prev-Stronger Bid Distance: Time Since the Last Strictly-Higher Bid Print
开始编码实现 solution(bids: list[float]) -> list[int]。给定一段长度为 N 的买价 print 流 bids,对每个下标 i(0 <= i < N)返回到最近一次满足 bids[j] > bids[i] 的更早 tick 的距离 i - j(严格更高),若不存在则返回 -1。
例:solution([2.0, 1.5, 1.5, 1.7, 3.0]) 返回 [-1, 1, 2, 3, -1]。第 0 个 tick 无更早 print,返回 -1;第 1 个 tick 1.5 看到一步之前的 2.0 严格更高,返回 1;第 2 个 tick 1.5 看到两步之前的 2.0 仍是最近一次严格更高 print(下标 1 的 1.5 等价不算更强),返回 2;第 3 个 tick 1.7 又看到三步之前的 2.0 是最近一次严格更高(1.5 < 1.7 所以中间的 1.5 都被主导),返回 3;第 4 个 tick 3.0 之前没有任何严格更高的 print(3.0 主导此前所有),返回 -1。
需要明确的细节:空输入返回 [];下标 0 永远返回 -1(没有更早的 tick);相等价格不算更强(采用严格大于语义);输出列表按位置 精确 比较(整数比较,不带浮点容差)。
朴素方案对每个 i 向左线性回溯,最坏情况下(如长升序列每个后续 tick 都要扫到起点)退化为 O(N^2),会在 N 接近上限的隐藏用例上超时;标准做法是单调递减栈维护 (下标, 价格) 对:每个 tick 弹出所有价格 <= bids[i] 的栈顶(这些都是 weaker-or-equal 且更远,对未来任何 tick 都不优于当前 i),然后读新的栈顶作为"上一次更强"答案。整体复杂度均摊 O(N)。
实现细节由 stubs/stub.py 提供。
实践背景
某场内买价 tape 监控仪表盘把"距上一次严格更高买价的时间"用作快速盘整/衰减压力指标:距离越大,意味着买方已经很久没有 print 出严格高于当前 quote 的新水位了,研究侧把这种情形视作买方靠在一个软压顶上、可能转弱的信号;返回 -1(不存在更早的更强买价)即"历史新高"标记,意味着当前 print 至少不低于此前任何一笔买价,仪表盘据此触发买方强势提示。直接对每个 tick 回溯扫描会让指标线程跟不上场内推送的 tape 速率,工程上必须把单步成本压成均摊 O(1)。严格大于的等价处理是有意为之:同价位的重复买价被视为同一强度状态的延续,而不是新的"更强"参照——所以回看会跨过等价 print 落在最近一次严格更高的 print 上。这一处理让指标在同价位被反复 hit(场内常见微结构)时保持稳定,只有当买方真正做出新高时,才会触发"无更早更强"重置。
约束条件
- 0 <= N <= 200000,其中 N 为 solution(bids) 的输入长度
- 每个 bids[i] 为 -1e9 到 1e9 之间的浮点数
- 输出为长度为 N 的 list[int],第 i 项是到最近一次严格更高的更早买价的距离,若不存在则为 -1
- "Stronger" 采用严格大于语义——相等价格不算更强
- 输出按位置精确比对(exact 比较),不允许浮点容差
样例
Case 1 · statement-example: equal-price ties skip, strict-greater 2.0 dominates until 3.0
输入: [[2,1.5,1.5,1.7,3]]
期望: [-1,1,2,3,-1]
tick 0 无更早 print → -1;tick 1 看到一步前的 2.0 严格更高 → 1;tick 2 跨过等价 1.5,落在两步前的 2.0 → 2;tick 3 跨过 1.5(小于 1.7),仍落在三步前的 2.0 → 3;tick 4 3.0 主导此前所有 → -1。
Case 2 · visible: strictly increasing bids - every i except 0 returns -1
输入: [[1,2,3,4,5]]
期望: [-1,-1,-1,-1,-1]
每一笔都是新高,没有任何更早的严格更高 print,故每个位置都返回 -1。
Case 3 · visible: strictly decreasing bids - every i returns 1
输入: [[5,4,3,2,1]]
期望: [-1,1,1,1,1]
每个新 tick 的紧邻前一笔都严格更高,最近一次更强买价就是 i-1,距离全部为 1(除 tick 0 为 -1)。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: equal-price ties skip, strict-greater 2.0 dominates until 3.0
输入: [[2,1.5,1.5,1.7,3]]
期望: [-1,1,2,3,-1]
tick 0 无更早 print → -1;tick 1 看到一步前的 2.0 严格更高 → 1;tick 2 跨过等价 1.5,落在两步前的 2.0 → 2;tick 3 跨过 1.5(小于 1.7),仍落在三步前的 2.0 → 3;tick 4 3.0 主导此前所有 → -1。
Case 2 · visible: strictly increasing bids - every i except 0 returns -1
输入: [[1,2,3,4,5]]
期望: [-1,-1,-1,-1,-1]
每一笔都是新高,没有任何更早的严格更高 print,故每个位置都返回 -1。
Case 3 · visible: strictly decreasing bids - every i returns 1
输入: [[5,4,3,2,1]]
期望: [-1,1,1,1,1]
每个新 tick 的紧邻前一笔都严格更高,最近一次更强买价就是 i-1,距离全部为 1(除 tick 0 为 -1)。