1488. 避免洪水泛滥 (opens new window)

1.贪心+优先级队列+TreeMap

基于贪心策略，每次选择“当前可抽水湖泊”中，洪水泛滥时刻最早的湖泊进行抽水，其中当前可抽水湖泊定义为，当前已经装满水的湖泊。小顶堆queue输出湖泊的泛滥时刻最提前的湖泊。

• 第一步首先需要记录<上次降雨时刻，洪水泛滥时刻>，采用Map辅助计算。其中key为水池编号，value为上次降雨时刻。
• 如果当前湖泊已经出现过，说明当前湖泊在第i天会发生泛滥，需要在（begintime，i）区间内完成抽水。TreeMap存储每个泛滥湖泊的起始时间点信息，key为开始时间，value[0]为结束时间，value[1]为湖泊编号。
• 第二部贪心抽水，当前如果不降雨，则取出所有在第i天之前会发生泛滥的湖泊信息。并存入小顶堆，每次抽水都从堆顶取出泛滥时刻最邻近的湖泊。

class Solution {
    public int[] avoidFlood(int[] rains) {
        int[] res=new int[rains.length];
        Map<Integer,Integer> map=new HashMap<>();
        TreeMap<Integer,int[]> time=new TreeMap<>();
        PriorityQueue<int[]> queue=new PriorityQueue<>(new Comparator<int[]>(){
            public int compare(int[] o1,int[] o2){
                return o1[1]-o2[1];
            }
        });
        //拿到每个会发生洪水的区间
        for(int i=0;i<rains.length;i++){
            if(rains[i]!=0){
                if(map.containsKey(rains[i])){
                    int begintime=map.get(rains[i]);
                    time.put(begintime,new int[]{i,rains[i]});
                }
                map.put(rains[i],i);
                res[i]=-1;
            }
        }
        //贪心抽取最邻近要溢出的水库
        for(int i=0;i<rains.length;i++){
            if(rains[i]==0){
                while(time.size()>0&&time.firstKey()<i){
                    int start=time.firstKey();
                    int[] nums=time.get(start);
                    int end=nums[0];
                    int lake=nums[1];
                    time.remove(start);
                    queue.offer(new int[]{start,end,lake});
                }
                if(queue.size()==0){
                    res[i]=1;
                    continue;
                }
                int[] peek=queue.poll();
                if(peek[1]<=i) return new int[0];
                res[i]=peek[2];
            }
        }
        if(queue.size()>0||time.size()>0) return new int[0];
        return res;
    }
}