How do I avoid floods in the 'Avoid Flood in The City' problem?

Track the last rain day for each lake using a hash table, then choose the lake to dry based on the last rainy day using a greedy approach.

What is the time complexity of the solution for this problem?

The time complexity depends on your chosen approach; a hash table offers O(1) operations, while a heap or priority queue offers O(log n) operations.

What if no lake needs to be dried?

If the array contains no 0s, meaning there's no dry-day event, no action is required, and the lakes will flood.

How do I handle cases where drying a lake results in a flood?

If no dry day is available without causing a flood, return an empty array as it's impossible to avoid flooding.

Can this problem be solved using a dynamic programming approach?

This problem is more about array scanning and greedy choices rather than dynamic programming, as you need to decide when and which lake to dry efficiently.

#1488

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

避免洪水泛滥

你的国家有 10 9 个湖泊，所有湖泊一开始都是空的。当第 n 个湖泊下雨前是空的，那么它就会装满水。如果第 n 个湖泊下雨前是满的，这个湖泊会发生洪水。你的目标是避免任意一个湖泊发生洪水。给你一个整数数组 rains ，其中： rains[i] > 0 表示第 i 天时，第 rains[…

数组哈希表二分查找贪心堆（优先队列）

题目描述

你的国家有 10⁹ 个湖泊，所有湖泊一开始都是空的。当第 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 天选择抽干的湖泊。

如果有多种可行解，请返回它们中的 任意一个 。如果没办法阻止洪水，请返回一个 空的数组 。

请注意，如果你选择抽干一个装满水的湖泊，它会变成一个空的湖泊。但如果你选择抽干一个空的湖泊，那么将无事发生。

示例 1：

输入：rains = [1,2,3,4]
输出：[-1,-1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，装满水的湖泊包括 [1,2,3]
第四天后，装满水的湖泊包括 [1,2,3,4]
没有哪一天你可以抽干任何湖泊的水，也没有湖泊会发生洪水。

示例 2：

输入：rains = [1,2,0,0,2,1]
输出：[-1,-1,2,1,-1,-1]
解释：第一天后，装满水的湖泊包括 [1]
第二天后，装满水的湖泊包括 [1,2]
第三天后，我们抽干湖泊 2 。所以剩下装满水的湖泊包括 [1]
第四天后，我们抽干湖泊 1 。所以暂时没有装满水的湖泊了。
第五天后，装满水的湖泊包括 [2]。
第六天后，装满水的湖泊包括 [1,2]。
可以看出，这个方案下不会有洪水发生。同时， [-1,-1,1,2,-1,-1] 也是另一个可行的没有洪水的方案。

示例 3：

输入：rains = [1,2,0,1,2]
输出：[]
解释：第二天后，装满水的湖泊包括 [1,2]。我们可以在第三天抽干一个湖泊的水。
但第三天后，湖泊 1 和 2 都会再次下雨，所以不管我们第三天抽干哪个湖泊的水，另一个湖泊都会发生洪水。

提示：

1 <= rains.length <= 10⁵
0 <= rains[i] <= 10⁹

lightbulb

解题思路

方法一：贪心 + 二分查找

我们将所有晴天都存入 $sunny$ 数组或者有序集合中，使用哈希表 $rainy$ 记录每个湖泊最近一次下雨的日期。初始化答案数组 $ans$ 每个元素为 $-1$ 。

接下来，我们遍历 $rains$ 数组。对于每个下雨的日期 $i$ ，如果 $rainy[rains[i]]$ 存在，说明该湖泊在之前下过雨，那么我们需要找到 $sunny$ 数组中第一个大于 $rainy[rains[i]]$ 的日期，将其替换为下雨的日期，否则说明无法阻止洪水，返回空数组。对于没下雨的日期 $i$ ，我们将 $i$ 存入 $sunny$ 数组中，并且将 $ans[i]$ 置为 $1$ 。

遍历结束，返回答案数组。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为 $rains$ 数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        n = len(rains)
        ans = [-1] * n
        sunny = SortedList()
        rainy = {}
        for i, v in enumerate(rains):
            if v:
                if v in rainy:
                    idx = sunny.bisect_right(rainy[v])
                    if idx == len(sunny):
                        return []
                    ans[sunny[idx]] = v
                    sunny.discard(sunny[idx])
                rainy[v] = i
            else:
                sunny.add(i)
                ans[i] = 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for efficient use of hash table or priority queue.
question_mark
Evaluate the approach to handle the greedy choice of drying lakes.
question_mark
Check if the candidate can explain time and space complexities in terms of their solution.

warning

常见陷阱

外企场景

error
Failing to correctly track the last rain day for each lake, leading to wrong dry-day decisions.
error
Choosing the wrong lake to dry, causing a flood despite avoiding it initially.
error
Not considering edge cases where drying any lake leads to a flood.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if there’s no lake to dry (i.e., no 0 in the array)?
arrow_right_alt
How would you modify your approach if multiple lakes can be dried on the same day?
arrow_right_alt
Can you optimize the space usage while still maintaining O(log n) time complexity?

help

常见问题

外企场景

继续练习

#1338 数组大小减半 #1648 销售价值减少的颜色球 #1054 距离相等的条形码