LeetCode 1488. 避免洪水泛滥：哈希（贪心）

【LetMeFly】1488.避免洪水泛滥：哈希（贪心）

力扣题目链接：https://leetcode.cn/problems/avoid-flood-in-the-city/

你的国家有无数个湖泊，所有湖泊一开始都是空的。当第 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 <= 105
• 0 <= rains[i] <= 109

方法一：哈希（贪心）

思路

使用有序集合（例如C++的set）记录当前哪天没下雨并且没“被征用”；使用哈希表记录某湖的上次下雨日期。

需要明白的是，某湖的第一次下雨并不需要管，也不需要立刻抽水，只需要记下来就行了。当它再次下雨时，从上次下雨后没下雨且没被征用的一天中选尽可能早的一天，来抽取此湖の水就好了。

为什么在符合条件的“天”中，要选“尽可能早”的一天？因为对于没有下雨的两天d1和d2，$(d1,d2)$之间某天下雨的湖，只有$d2$能抽这个湖的水。

• 时间复杂度$O(len(rains)\log len(rains))$
• 空间复杂度$O(len(rains))$

AC代码

C++

class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        set<int> whenNotRain;
        unordered_map<int, int> whichAndWhen;
        vector<int> ans(rains.size(), 1);  // 没有0号湖
        for (int i = 0; i < rains.size(); i++) {
            if (!rains[i]) {
                whenNotRain.insert(i);
                continue;
            }
            ans[i] = -1;
            if (whichAndWhen.count(rains[i])) {
                int lastRainDay = whichAndWhen[rains[i]];  // 找一个lastRainDay后的晴天
                set<int>::iterator it = whenNotRain.upper_bound(lastRainDay);
                if (it == whenNotRain.end()) {
                    return {};
                }
                ans[*it] = rains[i];
                whenNotRain.erase(it);
            }
            whichAndWhen[rains[i]] = i;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Python

# from typing import List
from sortedcontainers import SortedList


class Solution:
    def avoidFlood(self, rains: List[int]) -> List[int]:
        whenNotRain = SortedList()
        whichAndRain = {}
        ans = [1] * len(rains)
        for i in range(len(rains)):
            if not rains[i]:
                whenNotRain.add(i)
                continue
            ans[i] = -1
            if rains[i] in whichAndRain:
                lastRainDay = whichAndRain[rains[i]]
                it = whenNotRain.bisect_right(lastRainDay)
                if it == len(whenNotRain):
                    return {}
                ans[whenNotRain[it]] = rains[i]
                whenNotRain.discard(whenNotRain[it])
            whichAndRain[rains[i]] = i
        return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/133809999