题目
解法：贪心
总体思想是把0的位置储存下来。每当遇到已经满的湖泊，查看两个问题：1）是否能够干燥他 2）能干燥他的符合条件的最早位置
不能干燥有两种情况，一种是现在就没有保存好的0，第二种是，保存好的0出现在这个湖泊之前被下雨满的时间之前。
能干燥的情况，我们遵循贪心思想，找到最早的符合条件的干燥日。也就是之前湖泊下满之后出现的第一个0，这边用二分搜索找到这个位置。
bisect.bisect_right(array, index)返回array中从左往右第一个比index大的位置
class Solution:def avoidFlood(self, rains: List[int]) -> List[int]:# main idea: 1) if encounter a zero, we store it's index and append 1 2) if not zero, we will find the previous position of the rained lake, and try to see if we can find a day to dry this lake ahead of time. This day must be after the previous rain day of this laken = len(rains)# list of zero daysdry_days = []# dict storing the full lakes id and day id pairfull_lakes = {
}ans = []for i in range(n):# if current day does not rain, add to dry list and answer append 1if rains[i] == 0:dry_days.append(i)ans.append(1)else:if rains[i] in full_lakes:# if encounter a rain to a lake but no dry day can use, return []if len(dry_days)==0:ans = []breakelse:# find the previous day when rain full this lakeindex = full_lakes[rains[i]]# find the first zero position after this index day, that is the earliest time we can dry this lakedry_pos=bisect.bisect_right(dry_days, index)# if no valid position found, return []if dry_pos>=len(dry_days):ans = []break# else, replace the prefilled 1 as the dried lake idelse:ans[dry_days[dry_pos]] = rains[i]dry_days.pop(dry_pos)# if the 'if' statement is not executed, means current rain is on a empty lake, so we add element to the full_lakes; Otherwise, we update the full lake id, they are all the same codefull_lakes[rains[i]] = i# no matter what happens, we will add -1 to the answerans.append(-1)return ans
二刷
总体思路：关键在于当碰到已经满了的湖再次下雨时如何处理。需要从逻辑和贪心两方面同时满足。从逻辑上讲，需要找到在这个湖上一次变满的后面的某天来清空这个湖。其次从贪心上讲找的这一天要尽量靠近
针对上面两个点，需要以下的关键操作：
- 首先需要一个map来储存lake:last_full_day的映射关系，这样当某个湖再次下雨时，我们就能快速找到之前变满的一天
- 其次需要知道变满的这一天后面第一个可以干燥的日子，所以用set+lower_bound结合。set是天然有序的，lower_bound用logn找到符合条件的那一天。其实用vector也可以，只是set删除一个元素的复杂度会比vector低。至于set erase的复杂度，感觉没有定论，不太说得清，但应该是比O(n)要低
class Solution {
public:vector<int> avoidFlood(vector<int>& rains) {
// saves the full lake as key and the day it gets fulled as valueunordered_map<int,int> full_lakes;// set to save the days that can dry lake in order. Have to choose set because it automatically saves the dry days in order// thus it will naturally be sortedset<int> dry_days;vector<int> ans;for(int i=0;i<rains.size();i++){
if(rains[i] == 0){
// if no rain today, we insert this day to dry days dry_days.insert(i);// but we don't know which lake to dry it, so put anylake here, it will get overwritten otherwise no hurt to dry some random lakeans.push_back(1);}else{
int lake = rains[i];// if this lake is already fullif(full_lakes.count(lake)){
// find the day when it became fullint full_day = full_lakes[lake];// try to find a day that can dry this lake after the day it gets full// greedy way, we dry it with the nearst dry_day// use upper_bound to find this nearest day// no difference of lower_boud or upper_bound here aince all vals are differentauto p = dry_days.upper_bound(full_day);// if we can't find such day, means we can't prevent the floodif(p == dry_days.end()) return {
};int dry_day = *p;// erase by pointer is much faster because we don't need to find this element anymoredry_days.erase(p);ans[dry_day] = lake;}full_lakes[lake] = i;ans.push_back(-1);}}return ans;}
};
时间复杂度：O(nlogn),logn来源于二分搜索，如果set的erase操作也是低于logn的话
空间复杂度：O(n)