Leetcode 1488. 避免洪水泛滥（DAY 189）---- 二分查找学习期

爱被打了一巴掌 2022-09-15 15:48 148阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]

--------------------

## 代码实现（首刷自解） ##

--------------------

class Solution { 
    public:
        vector<int> avoidFlood(vector<int>& rains) { 
            unordered_map<int,int> map;
            set<int> set;
            vector<int> ret(rains.size(),-1);
            for(int i=0;i<rains.size();++i)
            { 
                if(!rains[i])
                { 
                    set.emplace(i);
                    ret[i] = 1;
                }
                else
                { 
                    if(map.find(rains[i]) == map.end())  map[rains[i]] = i;
                    else
                    { 
                        auto iter = set.lower_bound(map[rains[i]]);
                        if(iter == set.end())
                        { 
                            ret.clear();
                            break;
                        }
                        else
                        { 
                            ret[*iter] = rains[map[rains[i]]];
                            set.erase(iter);
                            map[rains[i]] = i;
                        }
                    }
                }
            }
            return ret;
        }
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBATG92ZSA2_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/436934d0547e43868de9f0dda1fc3a36.png