leetcode 1488 洪水泛滥

贪心加二分。

当遇到下雨天时答案对应位置返回-1即可。然后这道题的重点就在于当晴天的时候要放干哪些池的水，选择正确的话就会避免洪水。如果不能放好水的话就会发生洪水返回[]。

但是怎么做正确选择呢？也就是说要知道后面哪个池又一次下雨了，才能根据贪心法则做选择在这个池第二次下雨之前放干水，根据贪心法则选择最接近第一次下雨的晴天，也就是尽早放干水越好。

请注意这里选择放干水的晴天必须在第一次下雨和第二次下雨之间，所以选择在此之间且在第一次下雨之后最接近的就可以。

这样的话，就遍历数组，如果大于0说明下雨，答案数组直接赋值为-1，然后将池塘的下雨日期用hashmap记录下来，即记录池塘上一次下雨的时候，当再次遇到的时候，可以根据记录得到第一次下雨和第二次下雨的两个日期。

当等于0的话把日期记录在数组中，然后在池塘第二次下雨的时候，在数组中找出大于第一次下雨日期且最接近的日子。也就是在晴天数组中找到在此范围内[第一次下雨+1，第二次下雨]最小的值。那就是二分查找，目标为第一次下雨日期。

因为数组中日期记录为升序，所以可以根据二分查找，这里必须要查找，直接返回第一个值等都是不行的。

然后把答案数组赋值抽干的池，此时下雨天也已经被用过了，直接删除，这样下次就找不到它了。
然后把hashmap中池塘下雨的日期更改。

而且请注意，题目中数组长度最大为10^5如果平方会超时的，只能线性方法或者logn这种，往这个上面去思考。
注意
import bisect
bisect.bisect_left(list,x) 如果元素存在，插入点左侧，如果不存在，返回插入点的位置，返回的是大于的数字
bisect.bisect_right(list,x) 如果元素在数组中存在，返回插入点右侧，如果不存在返回插入点的位置,返回的是大于的数字

import bisect
class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        hashmap={}
        ans=[0 for _ in range(len(rains))]
        norain=[]
        for i in range(len(rains)):
            if rains[i]>0:
                ans[i]=-1
                if rains[i] not in hashmap or len(hashmap)==0:
                    hashmap[rains[i]]=i




                else:

                    if len(norain)!=0:
                        target=hashmap[rains[i]]
                        left=0
                        right=len(norain)-1
                        while left<=right:
                            mid=(right-left)//2+left
                            if norain[mid]>target:
                                right=mid-1
                            elif norain[mid]<target:
                                left=mid+1
                        #left=bisect.bisect_left/right(norain,target)
                        if left>=len(norain):
                            return []
                        ans[norain[left]]=rains[i]
                        norain.remove(norain[left])
                        hashmap[rains[i]]=i


                    else:
                        return []

            elif rains[i]==0:
                norain.append(i)

        if len(norain)!=0:


            for i in norain:
                ans[i]=1

        return ans

import bisect
class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        hashmap={}
        ans=[0 for _ in range(len(rains))]
        norain=[]
        for i in range(len(rains)):
            if rains[i]>0:
                ans[i]=-1
                if rains[i] not in hashmap or len(hashmap)==0:
                    hashmap[rains[i]]=i

                else:

                    if len(norain)!=0:
                        target=hashmap[rains[i]]
                        left=bisect_right(norain,target)
                        if left>=len(norain):
                            return []
                        ans[norain[left]]=rains[i]                     
                        norain.remove(norain[left])
                        hashmap[rains[i]]=i

                    else:
                        return []
            else
                ans[i]=1
                norain.append(i)


        return ans

使用堆

import bisect
class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        hashmap=collections.defaultdict(list)
        #hashmap=collections.defaultdict(collections.deque)
        ans=[0 for _ in range(len(rains))]
        norain=[]
        q=[]
        full=[]
        for i in range(len(rains)):
            if rains[i]!=0:
                ans[i]=-1
                hashmap[rains[i]].append(i)
            else:
                ans[i]=1
                norain.append(i)
        for i in range(len(rains)):
            if rains[i]!=0:
                if rains[i] in full:
                    return []
                if len(hashmap[rains[i]])>1:

                    hashmap[rains[i]].pop(0)
                    full.append(rains[i])
                    if len(hashmap[rains[i]])!=0:
                        heapq.heappush(q,hashmap[rains[i]][0])#把下一个时间加入堆

            else:
               if len(q)!=0 :
                   item=heapq.heappop(q)
                   ans[i]=rains[item]
                   full.remove(rains[item])


        if len(q)!=0:
            return []
        return ans