收益流中包含 K 个幅度跳点的最短窗口
Shortest Window Containing K Magnitude Spikes in a Return Stream
开始编码实现 solution(returns: list[float], T: float, K: int) -> int。给定一段逐期收益序列 returns、幅度阈值 T、以及目标 spike 数 K,返回最短的连续窗口长度——窗口内至少有 K 个索引 i 满足 abs(returns[i]) > T(严格大于,绝不允许等于)。若不存在此类窗口,返回 -1。特殊情形:K == 0 时无论输入如何均返回 0(空窗口已满足条件);returns 为空且 K >= 1 时返回 -1。
窗口"长度"指的是闭区间索引跨度 right - left + 1,并不是窗口内 spike 的个数。在所有至少包含 K 个 spike 的候选窗口中,要找的是长度最小者。spike 幅度并列(例如两个幅度相等的尖峰)不影响答案,因为 spike 判定只是关于 abs(returns[i]) 的严格不等式。
朴素的双重循环对每对 (left, right) 数一遍 spike,复杂度 O(N^2),在大规模压力测试上会超时。预期解法是一次线性扫描的双指针 / 可变窗口:在 spike 数 < K 时推进 right,在 spike 数 >= K 时收缩 left,每次收缩都用当前长度更新答案。
函数骨架见 stubs/stub.py。
实践背景
"spike 聚集检测器"是一种常见的定量市态标识:给定收益流和幅度阈值(用于界定何为显著行情),问题在于 K 个这样的显著行情可以多紧密地同时出现——最紧的这种窗口即是一种与模型无关的"显著事件聚集度"度量。聚集度高与跳点相关市态(波动率激增、新闻级联、流动性冲击)相关,执行台用该指标来约束仓位或切换到更保守的参数集。由于行情数据在线流式消费,检测器即便在 N 达到上万级别也必须维持 O(N)。
约束条件
- 0 <= len(returns) <= 5000;每个元素为有限浮点数,绝对值不超过 100
- T 为有限非负浮点数,范围 [0, 100];spike 判定为严格不等式:索引 i 是 spike 当且仅当 abs(returns[i]) > T(等于不算 spike)
- K 为整数;若 K == 0 则返回 0;若 K < 0 视同 K = 0(返回 0);一般情况下 K 落在 [1, len(returns)] 内
- 若不存在任何连续窗口包含至少 K 个 spike,返回 -1;否则返回最短合格窗口的整数长度
- 输出为整数,使用精确比对(不引入浮点容差)
样例
Case 1 · statement-example: two spikes inside a tight 2-wide window
输入: [[0.001,0.06,-0.002,0.003,0.07,-0.08,0.001,0.002],0.05,2]
期望: 2
abs(returns) 中超过阈值 0.05 的索引为 1、4、5。要让窗口至少包含 2 个 spike,最短做法为右端点 5、左端点 4 的窗口(长度 2),其包含索引 4 与 5 两个 spike。
Case 2 · statement-example: K equals total spikes spanning the array
输入: [[0.2,0,0,0,-0.3],0.1,2]
期望: 5
spike 在两端(索引 0 与 4),要同时包含两个 spike 必须覆盖 [0..4],长度为 5。
Case 3 · statement-example: strict > means equal magnitudes don't qualify
输入: [[0.05,-0.05,0.05],0.05,1]
期望: -1
三个元素的绝对值均为 0.05,并不严格大于阈值 0.05,故没有 spike,返回 -1。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · statement-example: two spikes inside a tight 2-wide window
输入: [[0.001,0.06,-0.002,0.003,0.07,-0.08,0.001,0.002],0.05,2]
期望: 2
abs(returns) 中超过阈值 0.05 的索引为 1、4、5。要让窗口至少包含 2 个 spike,最短做法为右端点 5、左端点 4 的窗口(长度 2),其包含索引 4 与 5 两个 spike。
Case 2 · statement-example: K equals total spikes spanning the array
输入: [[0.2,0,0,0,-0.3],0.1,2]
期望: 5
spike 在两端(索引 0 与 4),要同时包含两个 spike 必须覆盖 [0..4],长度为 5。
Case 3 · statement-example: strict > means equal magnitudes don't qualify
输入: [[0.05,-0.05,0.05],0.05,1]
期望: -1
三个元素的绝对值均为 0.05,并不严格大于阈值 0.05,故没有 spike,返回 -1。