← 返回编程题库
coding-shortest-window-k-spikes中等免费版2000ms未尝试

收益流中包含 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 可见样例;服务端提交会运行可见样例和隐藏测试。

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

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

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。