从每个起始日起累计库存达到目标量的最早结束日数
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] = 0、P[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 = 1 是 j = 3,所以 out[0] = 3。i = 1 时,最小这样的 j 仍是 3,长度为 3 - 1 = 2。i = 2 时 j = 3、长度 1。i = 3 与 i = 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] >= 4 是 j = 4,故 out[0] = 4。i = 1:需要 P[j] >= 7,不存在,故 -1。i = 2:需要 P[j] >= 5,最小为 j = 4,长度为 2。i = 3:需要 P[j] >= 4,最小为 j = 4,长度为 1。i = 4:需要 P[j] >= 9,只有 P[5] = 6,故 -1。i = 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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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 直接返回空列表。