← 返回编程题库
coding-earliest-cumvol-target-from-each-day中等免费版2000ms未尝试

从每个起始日起累计库存达到目标量的最早结束日数

Earliest End-Day Reaching A Cumulative Inventory Target From Each Starting Day

开始编码

实现 solution(daily_deltas: list[int], target: int) -> list[int]。给定长度为 N 的逐日库存净变动整数流 daily_deltas(正数表示买入、负数表示卖出)以及一个正整数 target。对每个起始日 i ∈ [0, N-1],返回最小的 j ∈ (i, N] 使得 sum(daily_deltas[i..j-1]) >= target,并以结束日数 j - i 表达——即从 i(含)到最早满足条件的结束位置(不含)之间的天数。如果不存在这样的 j,则 out[i] = -1

等价的前缀和表述。令 P[0] = 0P[k] = sum(daily_deltas[0..k-1])。对每个 i,求最小的 j > i 满足 P[j] - P[i] >= target,并返回长度 j - i。比较是非严格的:累计恰好达到 target 也算命中。

关键陷阱——负数破坏单调滑动窗口。由于 daily_deltas 允许出现负数,前缀和序列 P 单调,因此假设前缀和单调非降的双指针/滑动窗口在本题上会得出错误结果。预期解法是基于堆的前向扫描,复杂度 O(N log N),对非单调前缀和成立。

关键陷阱——输出的"单位"out[i]长度 j - i(天数),不是绝对结束下标 j。常见错误是把 out[i] 当作绝对下标,导致后续使用时偏移失配。

solution([0, 0, 1, 0, 0], 1) 返回 [3, 2, 1, -1, -1]。前缀和 P = [0, 0, 0, 1, 1, 1]i = 0 时,最小的 j 使 P[j] >= P[0] + 1 = 1j = 3,所以 out[0] = 3i = 1 时,最小这样的 j 仍是 3,长度为 3 - 1 = 2i = 2j = 3、长度 1i = 3i = 4 时累计变动再也无法到达 1,因此都为 -1

第二个含负数的例子——solution([3, -2, -1, 5, 1], 4) 返回 [4, -1, 2, 1, -1]。前缀和 P = [0, 3, 1, 0, 5, 6]i = 0:最小的 j 满足 P[j] >= 4j = 4,故 out[0] = 4i = 1:需要 P[j] >= 7,不存在,故 -1i = 2:需要 P[j] >= 5,最小为 j = 4,长度为 2i = 3:需要 P[j] >= 4,最小为 j = 4,长度为 1i = 4:需要 P[j] >= 9,只有 P[5] = 6,故 -1i = 1 处的答案就是负数陷阱的体现——若按"前缀和单调"假设做滑动窗口,会读到 3 + (-2) + (-1) + 5 + 1 = 6 并误判从 i = 1 起的长度 4 窗口"可以",但实际从该起始下标出发并不存在合法的前缀阈值达成点。

solution([], 5) 返回 []solution([5], 5) 返回 [1](单日即达目标)。solution([4], 5) 返回 [-1]

stubs/stub.py 中提供函数骨架。

实践背景

交易台拿到一份未来 N 个交易日的逐日库存净变动预测(正数为买入、负数为卖出),希望得到一个排程视图:如果在第 i 日开启一轮新的累计建仓周期,按预测要多少天才能从该起点累计买够 target 股?逐起始日的答案会喂给成交进度规划面板——out[i] 告诉交易员从每个候选起点出发的最早周期完成日,out[i] = -1 则代表"从该日起开仓,按预测永远累计不够;要么把起点推后,要么放宽目标"。daily_deltas 中的负值刻画了中间穿插的卖出日(再平衡、对冲反向、客户解仓),这些短暂回撤正是普通滑动窗口在本题失效的根源。

约束条件

  • 0 <= len(daily_deltas) <= 1500。空输入返回 `[]`。
  • 每个 daily_deltas[i] 为 [-1_000_000, 1_000_000] 区间内的整数。允许出现负数;这正是普通单调前缀和滑动窗口在本题上失效的原因。
  • 1 <= target <= 1_000_000_000。
  • 输出为长度 N 的列表。每个元素为 [1, N] 内的正整数(从起始日 `i` 计起到累计**首次**达到 `target` 的最早结束日的天数),或者哨兵 -1(不存在这样的结束日)。
  • 比对方式为精确比对(comparator 为 `exact`、有序)。

样例

Case 1 · statement-example: target=1 over [0,0,1,0,0]

输入: [[0,0,1,0,0],1]

期望: [3,2,1,-1,-1]

P=[0,0,0,1,1,1];i=0 最早 j=3 → 3;i=1 → 2;i=2 → 1;i=3,i=4 此后再无 1,故为 -1。

Case 2 · statement-example: negatives [3,-2,-1,5,1] target=4

输入: [[3,-2,-1,5,1],4]

期望: [4,-1,2,1,-1]

P=[0,3,1,0,5,6];i=0 j=4→4;i=1 需 P[j]>=7,不存在 → -1;i=2 j=4→2;i=3 j=4→1;i=4 需 P[j]>=9,不存在 → -1。

Case 3 · visible: empty list

输入: [[],5]

期望: []

N=0 直接返回空列表。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · statement-example: target=1 over [0,0,1,0,0]

输入: [[0,0,1,0,0],1]

期望: [3,2,1,-1,-1]

P=[0,0,0,1,1,1];i=0 最早 j=3 → 3;i=1 → 2;i=2 → 1;i=3,i=4 此后再无 1,故为 -1。

Case 2 · statement-example: negatives [3,-2,-1,5,1] target=4

输入: [[3,-2,-1,5,1],4]

期望: [4,-1,2,1,-1]

P=[0,3,1,0,5,6];i=0 j=4→4;i=1 需 P[j]>=7,不存在 → -1;i=2 j=4→2;i=3 j=4→1;i=4 需 P[j]>=9,不存在 → -1。

Case 3 · visible: empty list

输入: [[],5]

期望: []

N=0 直接返回空列表。