LeetCode 1488. 避免洪水泛滥
题目描述
题意分析
湖泊初始为空，下雨后装满；装满后未抽干就再次下雨，会发生洪水。雨天答案必须填
-1，晴天选择一个湖抽水，抽空湖也合法；无解时返回空数组。对同一湖的每两次相邻降雨，必须在它们之间安排至少一个晴天抽水。于是问题转为：每个降雨间隔占用一个合法晴天，同一天不能分配给两个湖。
解法：哈希记录湖泊 + 树状数组分配晴天
核心思路
[!blue]
从左到右处理日期，用
lastRain[lake]记录某湖上次下雨的日期。若它首次下雨，不产生抽水要求；否则设上次日期为pre、今天为i，必须从尚未分配的晴天中找一个满足pre < day < i的日期。选择其中最早的一天，把较晚晴天留给后续需求。这个贪心可以用交换说明。假设某个可行安排给当前需求用了较晚的晴天
t，而最早可用的s满足s <= t。若该安排没有用s，直接把当前需求移到s；若s被分给某个尚未处理的需求，就把那个需求移到t。因为它原本能使用s，其左端早于s，而右端又晚于当前日期i，所以s <= t < i保证t仍在它的合法区间内。交换不影响之前的分配，因此优先用最早晴天不会使原本可行的整体安排失效。用树状数组记录已经出现、尚未分配的晴天：日期
day对应位置day+1，可用记为1，否则为0。扫描只加入过去的晴天，所以树中所有候选都早于当前雨天，不必再检查右端。
usedBefore = sum(pre+1)数的是不晚于上次降雨的可用晴天，并不是已经使用的天数。若它等于全部可用晴天数，就没有落在合法区间内的日期，返回空数组；否则按日期排序后的第usedBefore+1个可用晴天，就是第一个严格晚于pre的候选。分配后将该位置减一，防止重复使用。
findByOrder(order)用树状数组找到第order个1。它从高到低尝试二进制步长，维护已经跳过的前缀idx和剩余名次。当前步长为step时，idx由更大的步长组成，所以tree[idx+step]恰好统计这次要跳过的新区间。若这一段数量小于剩余名次，就整段跳过并扣掉其数量；否则缩小步长继续寻找。结束时idx是目标之前的最后位置，返回idx+1。晴天先默认填湖泊
1，只有分配给降雨间隔时才改成目标湖。没有被使用的晴天抽任意湖都不会增加洪水风险；同一湖每个相邻降雨间隔都得到抽水机会，就足以保证整个方案合法。
解题步骤
- 遇到晴天，答案先填
1，并在树状数组位置i+1加一。- 遇到雨天，答案填
-1。若该湖从未下雨，直接记录当前日期。- 若存在上次降雨
pre，查询不晚于pre的可用晴天数，与全部可用数比较；没有更晚候选就返回空数组。- 用
findByOrder(usedBefore+1)找到最早合法晴天，填入该湖编号，并从树状数组删除这个候选。- 完成当前需求后再更新
lastRain[lake] = i。处理完全部日期后返回答案。
代码实现
class Solution {
public int[] avoidFlood(int[] rains) {
int n = rains.length;
int[] answer = new int[n];
Map<Integer, Integer> lastRain = new HashMap<>();
Fenwick dryDays = new Fenwick(n);
for (int i = 0; i < n; i++) {
int lake = rains[i];
if (lake == 0) {
answer[i] = 1;
// 原日期下标加一后进入树状数组，零下标不能参与更新。
dryDays.add(i + 1, 1);
continue;
}
answer[i] = -1;
if (lastRain.containsKey(lake)) {
int pre = lastRain.get(lake);
// 这里统计的是上次下雨之前尚未使用的晴天，不是已用天数。
int usedBefore = dryDays.sum(pre + 1);
if (dryDays.total() == usedBefore) {
return new int[0];
}
// 跳过过早的晴天，选第一个合法且尚未使用的日期。
int dryPos = dryDays.findByOrder(usedBefore + 1);
answer[dryPos - 1] = lake;
// 同一天不能分配给另一个湖，使用后删除。
dryDays.add(dryPos, -1);
}
// 完成本次需求后才更新上次下雨的位置。
lastRain.put(lake, i);
}
return answer;
}
private static class Fenwick {
private final int[] tree;
Fenwick(int n) {
tree = new int[n + 1];
}
void add(int idx, int delta) {
while (idx < tree.length) {
tree[idx] += delta;
idx += idx & -idx;
}
}
int sum(int idx) {
int answer = 0;
while (idx > 0) {
answer += tree[idx];
idx -= idx & -idx;
}
return answer;
}
int total() {
return sum(tree.length - 1);
}
int findByOrder(int order) {
int idx = 0;
int step = 1;
while (step < tree.length) {
step <<= 1;
}
while (step > 0) {
int next = idx + step;
if (next < tree.length && tree[next] < order) {
idx = next;
// 这一整段数量不足，跳过该段并扣掉其中的候选数。
order -= tree[next];
}
step >>= 1;
}
return idx + 1;
}
}
}
func avoidFlood(rains []int) []int {
n := len(rains)
answer := make([]int, n)
lastRain := make(map[int]int)
dryDays := newFenwick(n)
for i, lake := range rains {
if lake == 0 {
answer[i] = 1
// 原日期下标加一后进入树状数组，零下标不能参与更新。
dryDays.add(i+1, 1)
continue
}
answer[i] = -1
if pre, ok := lastRain[lake]; ok {
// 这里统计的是上次下雨之前尚未使用的晴天，不是已用天数。
usedBefore := dryDays.sum(pre + 1)
if dryDays.total() == usedBefore {
return []int{}
}
// 跳过过早的晴天，选第一个合法且尚未使用的日期。
dryPos := dryDays.findByOrder(usedBefore + 1)
answer[dryPos-1] = lake
// 同一天不能分配给另一个湖，使用后删除。
dryDays.add(dryPos, -1)
}
// 完成本次需求后才更新上次下雨的位置。
lastRain[lake] = i
}
return answer
}
type fenwick struct {
tree []int
}
func newFenwick(n int) *fenwick {
return &fenwick{tree: make([]int, n+1)}
}
func (f *fenwick) add(idx int, delta int) {
for idx < len(f.tree) {
f.tree[idx] += delta
idx += idx & -idx
}
}
func (f *fenwick) sum(idx int) int {
answer := 0
for idx > 0 {
answer += f.tree[idx]
idx -= idx & -idx
}
return answer
}
func (f *fenwick) total() int {
return f.sum(len(f.tree) - 1)
}
func (f *fenwick) findByOrder(order int) int {
idx := 0
step := 1
for step < len(f.tree) {
step <<= 1
}
for step > 0 {
next := idx + step
if next < len(f.tree) && f.tree[next] < order {
idx = next
// 这一整段数量不足，跳过该段并扣掉其中的候选数。
order -= f.tree[next]
}
step >>= 1
}
return idx + 1
}
复杂度分析
- 时间复杂度：期望 $O(n\log(n+1))$。哈希表操作期望为常数时间，每天只进行常数次树状数组更新、前缀和或按序号查找。
- 空间复杂度：$O(n)$。树状数组、上次降雨记录和答案数组都不超过日期数量级。
关键点总结
[!green]
- 每个重复降雨形成一个开区间抽水需求，扫描顺序就是需求右端从小到大的顺序。
- 选最早可用晴天可以通过交换保留整体可行性，不能任意占用较晚候选。
- 树状数组存的是可用晴天的数量，前缀和排除过早日期，序号查找定位剩余的第一个候选。
- 分配一个晴天后必须删除，再更新该湖的上次降雨日期。
易错点总结
[!yellow]
- 使用不晚于上次降雨的晴天，无法排空那次降雨带来的水；使用今天以后的晴天，则来不及阻止当前洪水。
- 随意选择最晚候选，可能占掉后续某个左端更靠后的需求唯一可用的晴天。
- 把
usedBefore当成已使用日期数，会误解第usedBefore+1个候选的含义。- 分配后不把树状数组该位置减一，会让同一天承担多个湖的抽水任务。
- 先覆盖
lastRain再查询会丢掉区间左端；树状数组更新使用原下标而不加一，则可能在位置0无法前进。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1353. 最多可以参加的会议数目 | 中等 | 每个两次降雨之间的湖泊需要占用一个可用晴天，可按时间约束调度，避免把早期空位浪费给宽松任务。 |
| 1705. 吃苹果的最大数目 | 中等 | 若按下一次降雨期限处理，和优先处理最早过期苹果一样，要先解决最紧迫的可用对象。 |