【刷题篇】避免洪水泛滥

一、题目

OJ链接

二、题解

2.1 大致思路

2.2 详细实现

2.3 源码

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Test1 {
    

    public static class Work implements Comparable<Work>{
    
        public int lake;
        public int nextRain;
        public Work(int l,int p) {
    
            lake=l;
            nextRain=p;
        }
        @Override
        public int compareTo(Work o) {
    
            return nextRain-o.nextRain;
        }
    }
    public static int[] avoidFlood(int[] rains) {
    

        int n= rains.length;
        int[] ans=new int[n];
        int[] invalid=new int[0]; //如果无法避免洪水泛滥，则返回这个空数组
         //map中用来存储，某个湖泊在哪天将下雨
        HashMap<Integer, LinkedList<Integer>> map=new HashMap<>();
        for (int i = 0; i < n; i++) {
    
            if(rains[i]!=0){
    
                if(!map.containsKey(rains[i])){
    
                    map.put(rains[i],new LinkedList<>());
                }
                map.get(rains[i]).addLast(i);
            }
        }
        HashSet<Integer> set=new HashSet<>();
        PriorityQueue<Work> heap=new PriorityQueue<Work>();
        for (int i = 0; i < n; i++) {
    
            if(rains[i]!=0){
    
                if(!set.contains(rains[i])){
    
                    set.add(rains[i]);
                     map.get(rains[i]).pollFirst();
                     if(!map.get(rains[i]).isEmpty()){
    
                         heap.add(new Work(rains[i],map.get(rains[i]).peekFirst()));
                     }
                     ans[i]=-1;
                }else {
    
                    return invalid;
                }
            }else {
    
                if(heap.isEmpty()){
    
                    ans[i]=1;
                }else {
    
                    Work cur=heap.poll();
                    set.remove(cur.lake);
                    ans[i]= cur.lake;
                }

            }
        }
        return ans;
    }
}