你的国家有无数个湖泊，所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的，那么它就会装满水。如果第 n 个湖泊下雨前是 满的 ，这个湖泊会发生 洪水 。你的目标是避免任意一个湖泊发生洪水。
给你一个整数数组 rains ，其中：
rains[i] > 0表示第i天时，第rains[i]个湖泊会下雨。rains[i] == 0表示第i天没有湖泊会下雨，你可以选择 一个 湖泊并 抽干 这个湖泊的水。
请返回一个数组 ans ，满足：
ans.length == rains.length- 如果
rains[i] > 0，那么ans[i] == -1。 - 如果
rains[i] == 0，ans[i]是你第i天选择抽干的湖泊。
如果有多种可行解，请返回它们中的 任意一个 。如果没办法阻止洪水，请返回一个 空的数组 。
请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生。
示例 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] 也是另一个可行的没有洪水的方案。
示例 3：
输入：rains = [1,2,0,1,2] 输出：[] 解释：第二天后，装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。 但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。
提示：
1 <= rains.length <= 1050 <= rains[i] <= 109
方法一：贪心 + 二分查找
将所有晴天都存入 sunny 数组或者有序集合中，使用哈希表 rainy 记录每个湖泊最近一次下雨的日期。初始化答案数组 ans 每个元素为 -1。
遍历 rains 数组，对于每个下雨的日期 rainy[rains[i]] 存在，说明该湖泊在之前下过雨，那么我们需要找到 sunny 数组中第一个大于 rainy[rains[i]] 的日期，将其替换为下雨的日期，否则说明无法阻止洪水，返回空数组。对于没下雨的日期 sunny 数组中，并且将 ans[i] 置为 1。
遍历结束，返回答案数组。
时间复杂度 rains 数组的长度。
class Solution:
def avoidFlood(self, rains: List[int]) -> List[int]:
n = len(rains)
ans = [-1] * n
sunny = []
rainy = {}
for i, v in enumerate(rains):
if v:
if v in rainy:
idx = bisect_right(sunny, rainy[v])
if idx == len(sunny):
return []
ans[sunny.pop(idx)] = v
rainy[v] = i
else:
sunny.append(i)
ans[i] = 1
return ansclass Solution {
public int[] avoidFlood(int[] rains) {
int n = rains.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
TreeSet<Integer> sunny = new TreeSet<>();
Map<Integer, Integer> rainy = new HashMap<>();
for (int i = 0; i < n; ++i) {
int v = rains[i];
if (v > 0) {
if (rainy.containsKey(v)) {
Integer t = sunny.higher(rainy.get(v));
if (t == null) {
return new int[0];
}
ans[t] = v;
sunny.remove(t);
}
rainy.put(v, i);
} else {
sunny.add(i);
ans[i] = 1;
}
}
return ans;
}
}class Solution {
public:
vector<int> avoidFlood(vector<int>& rains) {
int n = rains.size();
vector<int> ans(n, -1);
set<int> sunny;
unordered_map<int, int> rainy;
for (int i = 0; i < n; ++i) {
int v = rains[i];
if (v) {
if (rainy.count(v)) {
auto it = sunny.upper_bound(rainy[v]);
if (it == sunny.end()) {
return {};
}
ans[*it] = v;
sunny.erase(it);
}
rainy[v] = i;
} else {
sunny.insert(i);
ans[i] = 1;
}
}
return ans;
}
};func avoidFlood(rains []int) []int {
n := len(rains)
ans := make([]int, n)
for i := range ans {
ans[i] = -1
}
sunny := []int{}
rainy := map[int]int{}
for i, v := range rains {
if v > 0 {
if j, ok := rainy[v]; ok {
idx := sort.Search(len(sunny), func(i int) bool { return sunny[i] > j })
if idx == len(sunny) {
return []int{}
}
ans[sunny[idx]] = v
sunny = append(sunny[:idx], sunny[idx+1:]...)
}
rainy[v] = i
} else {
sunny = append(sunny, i)
ans[i] = 1
}
}
return ans
}