原题链接:
https://leetcode.cn/problems/avoid-flood-in-the-city/description

解法1： 贪心 + 二分

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
    贪心 + 二分
    晴天日期全部记录到set<int> zero
    hash 记录每个湖泊上一次下雨的日期 (这里注意是只用记录上一次下雨的日期即可 操作的时候按顺序遍历 如果多于一次无法制止那么直接返回{} 即可)
*/
class Solution {
public:
    vector<int> avoidFlood(vector<int>& rains) {
        // 记录上一次降水的日期
        unordered_map<int,int>water;
        // 记录晴天
        set<int>zero;
        
        vector<int>ans(rains.size(),1);

        for(int i = 0 ; i < rains.size() ; i++){
            // 当天将要降水的湖泊
            int r = rains[i];
            
            // 晴天 -> 不降水
            if(r == 0){
                // 记录当前晴天日期
                zero.insert(i);
                continue;
            }

            // 雨天
            // 如果该湖泊之前降过水 则需要进行排水处理 否则会引发洪水 
            if(water.count(r) != 0){
                // 上一次降水的时间
                int pre = water[r];
                // 通过二分 在之前出现过的晴天 看是否有出现在pre之后的晴天
                auto it = zero.lower_bound(pre);
                // 没找到 那么只能是洪水
                if(it == zero.end()){
                    return {};
                }

                // 在找到的第一天晴天 处理当前湖泊
                ans[*it] = r;
                // 删除当前处理湖泊
                zero.erase(it);
            }

            // 记录该湖泊上一次降水的时间
            water[r] = i;
            // 当前天降水 不做任何操作记为-1
            ans[i] = -1;
        }

        return ans;
    }
};