---

1488. 避免洪水泛滥

• 标签：贪心、数组、哈希表、二分查找
• 难度：中等

题目链接

• 1488. 避免洪水泛滥 - 力扣

题目大意

描述：给定一个整数数组 $rains$，其中 $rains[i] > 0$ 表示第 $i$ 天在第 $rains[i]$ 个湖泊会下雨（该湖泊会充满水），$rains[i] = 0$ 表示第 $i$ 天可以抽干一个湖泊（选择任意一个湖泊将水抽干）。

要求：返回一个数组 $ans$，对于 $rains[i] = 0$ 的天，$ans[i]$ 表示抽干的湖泊编号。如果无法避免洪水（任何湖泊的水位达到 $2$），返回空数组。

说明：

• $1 \le rains.length \le 10^5$。
• $0 \le rains[i] \le 10^5$。

示例：

• 示例 1：

输入：rains = [1,2,3,4]
输出：[-1,-1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，装满水的湖泊包括 [1,2,3]
第四天后，装满水的湖泊包括 [1,2,3,4]
没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。

• 示例 2：

输入：rains = [1,2,0,0,2,1]
输出：[-1,-1,2,1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]
第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。
第五天后，装满水的湖泊包括 [2]。
第六天后，装满水的湖泊包括 [1,2]。
可以看出，这个方案下不会有洪水发生。同时， [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。

解题思路

思路 1：贪心 + 二分查找

1. 核心思想

当某个湖泊第二次下雨时，它必须在前一次下雨之后、本次下雨之前被抽干一次。因此：

• 记录每个湖泊上次下雨的位置（天索引）。
• 当遇到 $rains[i] = 0$ 时，记录这是一个可用的抽水日。
• 当遇到 $rains[i] = lake$ 时，检查 $lake$ 是否之前下过雨：
  • 如果之前下过，则需要在上次下雨之后、本次下雨之前选择一个晴天抽干它。
  • 为了给未来留下更多选择，应该选择这个范围内最早可用的晴天。

因此可以用二分查找（在有序的可用的晴天索引列表中查找第一个大于上次下雨日期的）。

2. 具体步骤

第 1 步：初始化：

• $last\_rain[lake]$：湖泊 $lake$ 上一次下雨的天索引（$1$ 索引）。
• $dry\_days$：存储 $rains[i] = 0$ 的天索引（有序列表，使用平衡结构，Python 中用列表手动二分）。
• $ans[i] = 1$（默认抽干 $1$ 号湖泊）。

第 2 步：遍历 $i = 0 \to n-1$：

• 如果 $rains[i] = 0$：将 $i$ 加入 $dry\_days$ 列表，$ans[i]$ 后续填充。
• 如果 $rains[i] = lake$：
  • 如果 $lake$ 之前下过雨（$last\_rain[lake]$ 存在）：
    • 在 $dry\_days$ 中二分查找第一个大于 $last\_rain[lake]$ 的索引。
    • 如果找不到，返回空数组（无法避免洪水）。
    • 否则，用该天的 $ans$ 填入 $lake$，并从 $dry\_days$ 中移除。
  • 更新 $last\_rain[lake] = i$。
  • $ans[i] = -1$（下雨天不抽水）。

第 3 步：返回 $ans$。

3. 举例说明

以 $rains = [1, 2, 0, 0, 2, 1]$ 为例：

天	rain	操作	dry_days	说明
0	1	last[1]=0, ans[0]=-1	[]
1	2	last[2]=1, ans[1]=-1	[]
2	0	加入 dry_days	[2]	ans[2] 待定
3	0	加入 dry_days	[2,3]	ans[3] 待定
4	2	上次下雨在 1，dry_days 中找 >1 的第一个 → 2，ans[2]=2，移除 2；last[2]=4，ans[4]=-1	[3]
5	1	上次下雨在 0，dry_days 中找 >0 的第一个 → 3，ans[3]=1，移除 3；ans[5]=-1	[]

结果 $ans = [-1, -1, 2, 1, -1, -1]$。

思路 1：代码

import bisect

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        ans = [1] * n  # 默认值 1，下雨的天会被覆盖
        dry_days = []       # 晴天的索引列表（有序）
        last_rain = {}      # 湖泊 -> 最后一次下雨的索引

        for i, lake in enumerate(rains):
            if lake == 0:
                # 晴天，记录可抽水的日子
                dry_days.append(i)
            else:
                ans[i] = -1
                if lake in last_rain:
                    # 该湖泊之前下过雨，需要在前一次之后找个晴天抽干
                    prev = last_rain[lake]
                    # 找第一个大于 prev 的晴天
                    idx = bisect.bisect_right(dry_days, prev)
                    if idx == len(dry_days):
                        return []  # 无法避免洪水
                    # 用这个晴天抽干该湖泊
                    dry_day = dry_days.pop(idx)
                    ans[dry_day] = lake
                # 更新最后一次下雨的位置
                last_rain[lake] = i

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$，遍历 $n$ 天，每次二分查找和删除 $O(\log n)$。
• 空间复杂度：$O(n)$，$dry\_days$ 和 $last\_rain$ 各 $O(n)$。