← 返回编程题库
coding-earliest-window-sum-and-floor中等免费版2000ms未尝试

同时满足累计收益达到目标且窗口内单期不破下限的最早 K 期窗口

Earliest K-Period Window Whose Cumulative Return Meets A Sum Target And Whose Worst Single Period Stays Above A Floor

开始编码

实现 solution(returns: list[float], K: int, sum_target: float, floor_min: float) -> int。给定长度为 N 的逐期收益序列 returns0 <= N <= 5000)、固定的正整数窗口长度 K、累计目标 sum_target 与单期下限 floor_min,返回**最小的 0-indexed 起始下标 i**(i[0, N - K] 内),使得长度为 K 的窗口 returns[i .. i+K-1] 同时满足下面两条谓词:

sum(returns[i..i+K-1]) >= sum_target          # 累计收益谓词
min(returns[i..i+K-1]) >= floor_min           # 单期下限谓词

若不存在这样的窗口则返回 -1。两条谓词的比较都是非严格>=)—— 相等视为满足。在两种平凡情形下也用同一个哨兵 -1:当 len(returns) == 0、或 K > len(returns) 时,根本无法构造任何长度为 K 的窗口。

期望算法整体 O(N):窗口和走增量(每次滑动一次加、一次减),窗口最小值用一个按位置索引的单调递增双端队列维护。每到一个窗口右端点 i + K - 1,立即检查两条谓词;首次同时成立的起始下标即答案。

solution([0.1, 0.7, 0.9, 0.8, 0.4, 1.2, 1.0, 0.6], 3, 2.0, 0.5) 返回 1。六个长度为 3 的窗口:窗口 0 [0.1, 0.7, 0.9] sum=1.7、min=0.1 —— 累计未达且下限被破;窗口 1 [0.7, 0.9, 0.8] sum=2.4>=2.0 且 min=0.7>=0.5 —— 两条谓词同时成立,函数立即返回 1(该窗口的起始下标)并停止扫描。

对比:solution([0.6, 0.7, 0.9, 0.4, 1.2, 1.0, 1.5], 3, 2.5, 0.5) 返回 4。窗口 2 [0.9, 0.4, 1.2] 虽然 sum=2.5>=2.5,但 min=0.4<0.5 被下限挡住,触发;下限谓词正是这里的拦截者。首个两条都成立的窗口是窗口 4 [1.2, 1.0, 1.5](sum=3.7、min=1.0),因此函数返回 4

再看:solution([0.0, 1.0, 0.5, 0.5, 0.5, 0.0], 3, 5.0, 0.0) 返回 -1。所有长度为 3 的窗口和都不超过 2.0,没有任何窗口能让累计收益谓词成立,即使下限谓词在多处都成立,联合条件仍不可达,返回哨兵 -1

实践背景

收益流的运行方监控者希望在回测中找到最早那段长度为 K 的窗口:窗口的累计 pnl 达到目标,窗口内没有任何单期跌破设定的下限(视为"窗口内未发生单期爆仓")。两条谓词覆盖不同的风险维度:累计目标筛掉总收益不够的窗口,单期下限筛掉那种"靠几次大涨平均掉一次大跌"才"勉强"达到累计目标的窗口。下游诊断对齐需要的是最早这样的窗口——首次联合通过事件的前沿位置——而不是这类窗口的计数,也不是累计最大的那个窗口。-1 表示"该 tape 上没有联合通过的窗口"。本题与单谓词滑动求和扫描器(只有一个聚合、一次比较)不同,这里需要单调队列同时维护窗口最小值,以保证两条谓词都能 O(1) 推进。

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

约束条件

  • 0 <= len(returns) <= 5000;每个元素是有限有符号 float,绝对值不超过 1e6
  • 1 <= K;K 为正整数。当 1 <= K <= len(returns) 时存在合法的长度为 K 的窗口;当 K > len(returns)(含 len(returns) == 0 的情形)时不存在任何窗口,函数**必须**返回 -1
  • sum_target 与 floor_min 是有限 float,取值在 [-1e9, 1e9]
  • 两条谓词的比较都是**非严格**(>=);相等视为满足
  • 输出为最小的 0-indexed 窗口起始下标(两条谓词同时满足处),若无任何长度为 K 的窗口满足则返回 -1(含 len(returns) == 0 与 K > len(returns) 这两种平凡情形)

样例

Case 1 · statement-example: K=3 8-day tape both predicates first met at start 1

输入: [[0.1,0.7,0.9,0.8,0.4,1.2,1,0.6],3,2,0.5]

期望: 1

窗口 0 [0.1,0.7,0.9] sum=1.7 不达标;窗口 1 [0.7,0.9,0.8] sum=2.4>=2.0 且 min=0.7>=0.5,两个谓词同时成立,最早起始下标 1。

Case 2 · statement-example: K=3 floor blocks earlier sum-passing window

输入: [[0.6,0.7,0.9,0.4,1.2,1,1.5],3,2.5,0.5]

期望: 4

窗口 2 [0.9,0.4,1.2] 虽然 sum=2.5>=2.5 但 min=0.4<0.5 被下限挡住;首次同时满足两条的窗口起始下标为 4 ([1.2,1.0,1.5] sum=3.7、min=1.0)。

Case 3 · statement-example: K=3 no window satisfies both -> -1

输入: [[0,1,0.5,0.5,0.5,0],3,5,0]

期望: -1

sum_target=5.0 太大,所有长度 3 窗口的和都小于 5,没有窗口同时满足两条谓词,返回 -1。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · statement-example: K=3 8-day tape both predicates first met at start 1

输入: [[0.1,0.7,0.9,0.8,0.4,1.2,1,0.6],3,2,0.5]

期望: 1

窗口 0 [0.1,0.7,0.9] sum=1.7 不达标;窗口 1 [0.7,0.9,0.8] sum=2.4>=2.0 且 min=0.7>=0.5,两个谓词同时成立,最早起始下标 1。

Case 2 · statement-example: K=3 floor blocks earlier sum-passing window

输入: [[0.6,0.7,0.9,0.4,1.2,1,1.5],3,2.5,0.5]

期望: 4

窗口 2 [0.9,0.4,1.2] 虽然 sum=2.5>=2.5 但 min=0.4<0.5 被下限挡住;首次同时满足两条的窗口起始下标为 4 ([1.2,1.0,1.5] sum=3.7、min=1.0)。

Case 3 · statement-example: K=3 no window satisfies both -> -1

输入: [[0,1,0.5,0.5,0.5,0],3,5,0]

期望: -1

sum_target=5.0 太大,所有长度 3 窗口的和都小于 5,没有窗口同时满足两条谓词,返回 -1。