什么是网站跳出率,网站建设 投资预算,国家允许哪几个网站做顺风车,平台搭建工具有哪些你的国家有无数个湖泊#xff0c;所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的#xff0c;那么它就会装满水。如果第 n 个湖泊下雨前是 满的 #xff0c;这个湖泊会发生 洪水 。你的目标是避免任意一个湖泊发生洪水。
给你一个整数数组 rains #xff0c;其中…你的国家有无数个湖泊所有湖泊一开始都是空的。当第 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 天选择抽干的湖泊。 如果有多种可行解请返回它们中的 任意一个 。如果没办法阻止洪水请返回一个 空的数组 。
请注意如果你选择抽干一个装满水的湖泊它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊那么将无事发生。 思路 洪水定义为湖泊里面有水但仍继续下雨。rains[i]0时第i天可以抽干任意湖泊中的水。 使用贪心算法当第i天的第j个湖泊发生洪水时看看第j个湖泊刚有水后面的日子有没有可以抽水的天如果有则直接在那天抽水没有直接返回空集。 使用HashMap存储湖泊和降水的日期。使用TreeSet存储可以进行抽干操作的日期。如果第j的湖泊降雨时候看看HashMap中是否有该湖泊如果有取daytreeset.higher(hashMap.get(lake))有就更新ans[day]为lake没有就返回空集。贪心算法需要一个清晰的思路。
class Solution {public int[] avoidFlood(int[] rains) {int n rains.length;// 保存不下雨的天数TreeSetInteger dryDay new TreeSet();// 保存下雨的湖泊与天数MapInteger, Integer map new HashMap();int[] ans new int[n];Arrays.fill(ans, 1);for(int i0; irains.length; i) {int lake rains[i];if(lake 0) {dryDay.add(i);} else {ans[i] -1;if(map.containsKey(lake)) {Integer higher dryDay.higher(map.get(lake));if(higher null) {return new int[]{};}dryDay.remove(higher);ans[higher] lake;}// 更新下雨的湖泊与日期map.put(lake, i);}} return ans;}
}
