1488. Avoid Flood in The City

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.

Given an integer array rains where:

• rains[i] > 0 means there will be rains over the rains[i] lake.
• rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

• ans.length == rains.length
• ans[i] == -1 if rains[i] > 0.
• ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)

Example 1:

Input: rains = [1,2,3,4]
Output: [-1,-1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day full lakes are [1,2,3]
After the fourth day full lakes are [1,2,3,4]
There's no day to dry any lake and there is no flood in any lake.

Example 2:

Input: rains = [1,2,0,0,2,1]
Output: [-1,-1,2,1,-1,-1]
Explanation: After the first day full lakes are [1]
After the second day full lakes are [1,2]
After the third day, we dry lake 2. Full lakes are [1]
After the fourth day, we dry lake 1. There is no full lakes.
After the fifth day, full lakes are [2].
After the sixth day, full lakes are [1,2].
It is easy that this scenario is flood-free. [-1,-1,1,2,-1,-1] is another acceptable scenario.

Example 3:

Input: rains = [1,2,0,1,2]
Output: []
Explanation: After the second day, full lakes are  [1,2]. We have to dry one lake in the third day.
After that, it will rain over lakes [1,2]. It's easy to prove that no matter which lake you choose to dry in the 3rd day, the other one will flood.

Example 4:

Input: rains = [69,0,0,0,69]
Output: [-1,69,1,1,-1]
Explanation: Any solution on one of the forms [-1,69,x,y,-1], [-1,x,69,y,-1] or [-1,x,y,69,-1] is acceptable where 1 <= x,y <= 10^9

Example 5:

Input: rains = [10,20,20]
Output: []
Explanation: It will rain over lake 20 two consecutive days. There is no chance to dry any lake.

Constraints:

• 1 <= rains.length <= 10^5
• 0 <= rains[i] <= 10^9

---

给定一个数组rains，rains[i]表示第i天在第rains[i]的湖上下雨，湖被灌满，比如第四个例子，rains[0]=69表示第0天在第69号湖上下雨，第69号湖被灌满。如果rains[i]=0表示第i天不下雨，可以抽干某个湖。问每个不下雨的天，抽干哪个湖，能让任意一个湖都不至于出现水灾（被灌满之后又被下雨）。

很有意思的一个题，暴力方法是，每个不下雨的天，对于之前被灌满的湖，抽干未来第一个要下雨的湖。比如对于rains=[1,2,3,0,2,0,0]，当遇到第一个0时，我们选择抽干2号湖，因为下一天马上要在2号湖上下雨，如果不抽干2号湖，则会发生水灾，所以要抽干未来第一个要出现水灾的湖。但是这种时间复杂度是O(n^2)。

参考讨论区，更好的做法是，先记录所有不下雨的天，然后对于每一个下雨天，如果要下雨的湖之前没被灌满，则不用管；如果之前被灌满了，则需要在之前被灌满那天之后找一个不下雨的天，把这个湖抽干。所以维护一个堆heap/set，记录之前不下雨的天，后续直接用lower_bound查找符合的天。

完整代码如下：

class Solution {
public:
	vector<int> avoidFlood(vector<int>& rains) {
		int n = rains.size();

		vector<int> ans;
		unordered_map<int, int> full_lakes;
		set<int> dry_days;

		for (int i = 0; i < n; ++i) {
			if (rains[i] == 0) {
				dry_days.insert(i);
				ans.push_back(1); // 先随便填一个数，后续会覆盖，填入真正要抽干的湖编号
			}
			else {
				if (full_lakes.find(rains[i]) != full_lakes.end()) { // 这个湖之前就满了，需要抽干
					int last_day = full_lakes[rains[i]];
					set<int>::iterator it = dry_days.lower_bound(last_day); //从之前满的那天往后选不下雨的一天抽干
					if (it == dry_days.end()) {
						return {}; // 失败
					}
					ans[*it] = rains[i];
					dry_days.erase(it);
				}
				full_lakes[rains[i]] = i; // 填入新的下雨日期
				ans.push_back(-1);
			}
		}

		return ans;
	}
};

本代码提交AC，用时1040MS。