下一次更高报价的时间戳
Next Greater Quote Timestamp
开始编码做市数据组在回放一段按时间升序排列的中间价事件 quotes,每条记录形如 [时间戳, mid_quote],时间戳沿下标严格递增。对每个事件 i,桌组想知道中间价下一次严格走高需要多久——具体来说,找到时间戳最早的、mid 严格大于 quotes[i][1] 的后续事件并返回其时间戳;如果当天剩余时间内中间价再也没有创出新高,就返回 -1。这种「下一次上跳前瞻」是日内微观结构分析的基础信号:一个在 i 时刻入场的交易者要等多久才能看到更好的报价?它也常被用来给成交按「到下次上跳的时间」分桶,做毒性 / 逆向选择诊断。
请实现 solution(quotes: list[list]) -> list[int]。返回一个与 quotes 等长的整数列表;第 i 项是下一个 mid 严格大于 quotes[i][1] 的事件的时间戳,若不存在则为 -1。空输入返回 []。
示例 1:solution([[1, 10], [2, 8], [3, 12], [4, 11], [5, 15]]) 返回 [3, 3, 5, 5, -1]。下标 0(mid 10)首次被超过是在 ts=3(mid 12);下标 1(mid 8)同样首次被超过是在 ts=3;下标 2(mid 12)要等到 ts=5(mid 15);下标 3(mid 11)也是 ts=5;下标 4 之后没有事件,返回 -1。
示例 2:solution([[1, 5], [2, 5], [3, 5]]) 返回 [-1, -1, -1]。这些 mid 全部相等,从来没有「严格更大」过——「严格大于」语义下相等的 mid 不能互相解决对方。这就是把比较条件错写成 ≤ 时最容易踩的坑:那样会让下标 0 错误地在 ts=2 被解决。
示例 3:solution([[10, 100], [20, 80], [30, 60], [40, 40]]) 是一段严格递减的盘口——后续 mid 永远不会超过此前任意 mid——所以答案是 [-1, -1, -1, -1]。
朴素的双重循环是 O(N²),N = 10⁵ 时必超时。正确工具是一个单调递减栈,栈里存放还没找到答案的下标。从左到右扫一遍,对每个新事件(mid = m):弹出所有栈顶 mid < m 的下标(这些下标的「下一次更大」恰好就是当前时间戳,弹出时一并写入答案),然后把当前下标压栈。栈中元素从底到顶始终保持「mid 严格递减」,每个下标至多被压入和弹出一次 → O(N) 时间,O(N) 额外空间。弹出条件用严格小于(< 而非 ≤)正是让相等 mid 不互相解决的关键。
约束条件
- 0 ≤ N = len(quotes) ≤ 100000
- 每个 quotes[i] 是长度 2 的列表 [ts, mid],ts 与 mid 都是整数
- 0 ≤ ts ≤ 10^9;时间戳沿 i 严格递增
- 0 ≤ mid ≤ 10^9
- 返回长度为 N 的列表;第 i 项是下一个严格更高 mid 的时间戳,若不存在则为 -1
样例
Case 1 · empty input
输入: [[]]
期望: []
空报价流,直接返回空列表。
Case 2 · single event — no future, returns [-1]
输入: [[[100,50]]]
期望: [-1]
只有一个事件,后面没有任何报价,自然不存在「下一次更高」,返回 [-1]。
Case 3 · mixed sample from problem statement
输入: [[[1,10],[2,8],[3,12],[4,11],[5,15]]]
期望: [3,3,5,5,-1]
下标 0(mid=10)、1(mid=8) 都在 ts=3(mid=12) 首次被严格超过;下标 2(mid=12)、3(mid=11) 都在 ts=5(mid=15) 解决;下标 4 之后无事件,返回 -1。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · empty input
输入: [[]]
期望: []
空报价流,直接返回空列表。
Case 2 · single event — no future, returns [-1]
输入: [[[100,50]]]
期望: [-1]
只有一个事件,后面没有任何报价,自然不存在「下一次更高」,返回 [-1]。
Case 3 · mixed sample from problem statement
输入: [[[1,10],[2,8],[3,12],[4,11],[5,15]]]
期望: [3,3,5,5,-1]
下标 0(mid=10)、1(mid=8) 都在 ts=3(mid=12) 首次被严格超过;下标 2(mid=12)、3(mid=11) 都在 ts=5(mid=15) 解决;下标 4 之后无事件,返回 -1。