LeetCode-1488. Avoid Flood in The City

LeetCode-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 chooseone lakethis day anddry it.

Return an array ​​ans​​

​​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​​

题解：

使用treeset存储所有不下雨的天，map存储<池塘，天数>索引，等到这个池塘再次下雨的时候set中返回比该天大的不下雨天，如果有，更新set，没有则返回空。

class Solution { public int[] avoidFlood(int[] rains) { int[] res = new int[rains.length]; HashMap map = new HashMap<>(); TreeSet set = new TreeSet<>(); for (int i = 0; i < rains.length; i++) { if (rains[i] == 0) { set.add(i); } else { if (map.containsKey(rains[i])) { Integer day = set.higher(map.get(rains[i])); if (day != null) { res[day] = rains[i]; set.remove(day); } else { return new int[0]; } } map.put(rains[i], i); res[i] = -1; } } for (int i : set) { res[i] = 1; } return res; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。