同时满足累计收益达到目标且窗口内单期不破下限的最早 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 的逐期收益序列 returns(0 <= 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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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。