基于降水量与每日用水量的储水容器最小容积计算求解

核心思路是跟踪整个周期内的水量结余变化，找到累计缺口的最大值——这就是容器需要的最小容积。

具体步骤 #

1. 计算每日净缺口：对每一天，计算 daily_gap = 用水量[i] - 降水量[i]：

   • 若 daily_gap > 0：当天用水量超出降水量，需从储水容器中支取对应水量
   • 若 daily_gap < 0：当天降水量有剩余，储水容器会增加 abs(daily_gap) 的水量

2. 追踪累计结余的最低值：

   • 初始化两个变量：
     • current_balance = 0：记录当前累计的水量结余（正数为存水，负数为未填补的缺口）
     • min_balance = 0：记录遍历过程中current_balance的最小值
   • 遍历每一天：
     • 更新current_balance = current_balance - daily_gap（减去净缺口：缺口为正则结余减少，缺口为负则结余增加）
     • 更新min_balance = min(min_balance, current_balance)

3. 确定最小容积：

   • 若 min_balance >= 0：全程无缺口，容器最小容积为0
   • 若 min_balance < 0：最大累计缺口为 abs(min_balance)，这就是所需的最小容器容积

为什么“找和最小的连续子数组”无效？ #

你之前的思路错误在于：我们需要的不是某个孤立时间段的缺口，而是从初始状态开始，累计下来的最低结余。前序天数的存水可以填补后续干旱期的缺口，单独截取干旱期的子数组会高估所需容积，而累计最低结余才是真正的最小缺口。

示例验证 #

假设：

• 降水量数组：[5, 0, 0, 3]
• 用水量数组：[2, 4, 4, 1]

每日净缺口：[-3, 4, 4, -2]

遍历过程：

• 第1天：current_balance = 0 - (-3) = 3 → min_balance 保持0
• 第2天：current_balance = 3 - 4 = -1 → min_balance 更新为-1
• 第3天：current_balance = -1 - 4 = -5 → min_balance 更新为-5
• 第4天：current_balance = -5 - (-2) = -3 → min_balance 保持-5

最终最小容积为 abs(-5) = 5，符合实际需求：前1天存的3份水，不足以覆盖后2天的8份缺口，需要额外5份储水才能度过。

内容的提问来源于stack exchange，提问作者Ali