← 返回编程题库
coding-min-cash-buffer-to-survive简单免费版2000ms未尝试

最小生存现金缓冲

Min Cash Buffer to Survive

开始编码

你在为一个交易桌计算开仓现金缓冲——未来 n 个交易日有一段已知的整数现金流:flows[i] > 0 表示第 i 天的结算流入,flows[i] < 0 表示追加保证金或资金流出。资金部要求找出**最小的开仓余额 B ≥ 0,使逐日叠加现金流后,运行余额任一日末都不会为负**(一旦当日收盘为负就触发透支告警,被迫紧急回购融资)。返回这个最小整数 B

请实现 solution(flows: list[int]) -> int。模拟规则很直接:bal = B 起步,然后每天 bal += flows[i];当且仅当每次更新后 bal >= 0B可行。你需要返回**最小可行 B**。示例:solution([3, -5, 2, -1]) 返回 2——以 B = 2 起步,余额轨迹是 2 → 5 → 0 → 2 → 1,全程非负;若 B = 1,第 2 天后会跌到 -1,不可行。边界:solution([]) 返回 0(没有任何义务要资助);solution([5, 3, 2]) 返回 0(只进不出,根本不用缓冲);solution([-1, -2, -3]) 返回 6(流出之和等于最深累计赤字)。

确实存在闭式 O(n) 解:B_min = max(0, -min(前缀和))。但本题的目的就是练习「二分答案」模板。配方:(1) 下界 lo = 0;(2) 上界 hi = sum(|flows|),足以覆盖任何最坏序列的现金缺口;(3) feasible(B) 谓词——O(n) 模拟一遍,返回「全程是否非负」;(4) 经典「下界二分」——while lo < hi,取 mid = (lo + hi) // 2,可行就 hi = mid,否则 lo = mid + 1。总开销 O(n log S),其中 S = sum(|flows|)。两条不可妥协的正确性约束:单调性(缓冲越大越可行——所有运行余额随之同步上移,原本非负的仍非负)和边界正确性hi = sum(|flows|) 必须永远可行;lo = 0 必须能涵盖「全程非负」的情形)。

约束条件

  • 0 ≤ len(flows) ≤ 100000
  • -1000000 ≤ flows[i] ≤ 1000000(正数为流入,负数为流出;整数)
  • 返回 int:最小的非负起始缓冲,使运行余额始终非负
  • 空 `flows` → 返回 0(没有任何待支付义务)
  • 若缓冲为 0 时所有运行余额已经 ≥ 0,返回 0

样例

Case 1 · classic mixed flows

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

期望: 2

B=2 时余额轨迹 2→5→0→2→1,全程非负;B=1 在第 2 天会跌到 -1,不可行。最深前缀和为 -2,故答案 = max(0, -(-2)) = 2。

Case 2 · empty flows

输入: [[]]

期望: 0

没有任何现金流义务,零缓冲就够。

Case 3 · all inflows — no buffer needed

输入: [[5,3,2]]

期望: 0

只进不出,所有前缀和都 ≥ 0,不需要任何起始缓冲。

最近提交

还没有提交记录。

编码区

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

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

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

Case 1 · classic mixed flows

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

期望: 2

B=2 时余额轨迹 2→5→0→2→1,全程非负;B=1 在第 2 天会跌到 -1,不可行。最深前缀和为 -2,故答案 = max(0, -(-2)) = 2。

Case 2 · empty flows

输入: [[]]

期望: 0

没有任何现金流义务,零缓冲就够。

Case 3 · all inflows — no buffer needed

输入: [[5,3,2]]

期望: 0

只进不出,所有前缀和都 ≥ 0,不需要任何起始缓冲。