类型：数组
-
- 避免洪水泛滥 💛 ⭐
https://leetcode-cn.com/problems/avoid-flood-in-the-city/
❓ 当一个湖泊所在地下雨的时候，若湖泊是空的，则湖泊会装满，若下雨前湖泊已经是满的，则湖泊会溢水。一共有 n 个湖泊。
给定一个数组 rains，其中：
- rains[i] > 0 表示第 i 天时，第 rains[i] 个湖泊会下雨。
- rains[i] == 0 表示第 i 天没有湖泊会下雨，你可以选择一个湖泊并抽干这个湖泊的水。
返回一个表示抽水方案的数组 ans，避免任一湖泊发生溢水。
- 如果 rains[i] > 0 ，那么 ans[i] == -1 。
- 如果 rains[i] == 0 ，ans[i] 是你第 i 天选择抽干的湖泊。
💡 贪心 - 事后诸葛亮
参见：力扣加加
我们贪心地想着把抽水用在最需要的地方，因此开始的时候能不抽就先不抽，但是把能抽水的时机存放在数组里，等到湖真的溢水了，我们后悔之前应该抽水的，此时才返回来修改之前的操作。
因此，我们遍历 rains 数组。
- rains[i] = 0，表示是晴天，我们不抽干任何湖泊，但是我们把 i 记录到 sunny 数组。
- rains[i] > 0，表示这个湖泊下雨了，我们去看看这个湖泊会不会溢水（我们用数组 lakes 来记录湖泊的状态）。
- 如果湖泊要溢水，我们就从 sunny 中找一个晴天去抽干它。要抽水的时候 sunny 为空，则说明溢水无法避免。
class Solution: def avoidFlood(self, rains: List[int]) -> List[int]: sunny = [] lakes = {} ans = [] for i, rain in enumerate(rains): if rain == 0: # 如果这天不下雨，那么不抽干任何湖泊，而是将该天加入 sunny 数组 sunny.append(i) ans.append(1) else: # 这天下雨了，看看会不会泛滥 ans.append(-1) if rain in lakes and lakes[rain] > -1: # 要泛滥了，应该在之前把它抽干 fullDay = lakes[rain] dryDay = -1 for index, day in enumerate(sunny): if day > fullDay: dryDay = day del sunny[index] break if dryDay == -1: # 没机会了 return [] ans[dryDay] = rain lakes[rain] = i return ans时间复杂度：O(n)，空间复杂度：O(n)