---
# System prepended metadata

title: 1488. Avoid Flood in The City
tags: [Leetcode, TreeMap, Medium]

---

# 1488. Avoid Flood in The City
###### tags: `Leetcode` `Medium` `TreeMap`
Link: https://leetcode.com/problems/avoid-flood-in-the-city/
## 思路 $O(NlogN)$ $O(N)$
用treeset存前面遇到的所有i rains[i]=0的地方
用map存所有之前被填满的lake和被填满的i
遍历rains 当发现现在的lake之前已经出现过的时候 就需要在empty里面找离它最近的rains=0的一天 用那一天来empty这个lake
## Code
```java=
class Solution {
    public int[] avoidFlood(int[] rains) {
        Map<Integer, Integer> map = new HashMap<>();
        TreeSet<Integer> empty = new TreeSet<>();
        int[] ans = new int[rains.length];
        for(int i=0; i<rains.length; i++){
            if(rains[i]==0) empty.add(i);
            else{
                if(map.containsKey(rains[i])){
                    Integer next = empty.ceiling(map.get(rains[i]));
                    if(next == null) return new int[0];
                    ans[next] = rains[i];
                    empty.remove(next);
                }
                ans[i] = -1;
                map.put(rains[i],i);
            }
        }
        for(int i:empty) ans[i] = 1;
        return ans;
    }
}
```