1488.避免洪水泛滥

链接：1488.避免洪水泛滥
难度：Medium
标签：贪心、数组、哈希表、二分查找、堆（优先队列）
简介：如果有多种可行解，请返回它们中的 任意一个 。如果没办法阻止洪水，请返回一个 空的数组 。请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生。

题解 1 - python

• 编辑时间：2023-10-13
• 执行用时：3896ms
• 内存消耗：31.44MB
• 编程语言：python
• 解法介绍：记录前一次蓄满水后，最近的放空时间。

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        full = dict()
        empty = []
        res = [-1] * len(rains)
        for i, rain in enumerate(rains):
            if rain == 0:
                empty.append(i)
            elif rain not in full:
                full[rain] = i
            else:
                l = bisect_left(empty, full[rain])
                if l == len(empty):
                    return []
                res[empty[l]] = rain
                full[rain] = i
                empty.pop(l)
        for o in empty:
            res[o] = 1
        return res