力扣1488.避免洪水泛滥

力扣1488.避免洪水泛滥

• 贪心 + 二分

  • 将所有晴天存入集合
  • 用哈希表存每次池子上一次下雨的日期
  • 当下雨并且池子满了时，二分找到上一次下雨之后最近的晴天

•   class Solution {unordered_map<int,int> mp;public:vector<int> avoidFlood(vector<int>& rains) {int n = rains.size();vector<int> ans(n,1);set<int> zero;for(int i=0;i<n;i++){int r = rains[i];//晴天存入集合if(r == 0){zero.insert(i);continue;}//下雨并且满了if(mp.count(r) != 0){//mp[r]为上一次下雨的日期 lowerbound找>mp[r]的第一个晴天日期auto it = zero.lower_bound(mp[r]);if(it == zero.end()) return {};ans[*it] = r;zero.erase(it);}//本次下雨池子和日期mp[r] = i;ans[i] = -1;}return ans;}};