1488题,洪水泛滥。在查找可用晴天时,如果使用 auto last_sunny_it = sunny.lower_bound(last_rain);就会超时。
而如果使用auto last_sunny_it = lower_bound(sunny.begin(),sunny.end(),last_rain); 就可以通过,性能较好。这2个lower_bound有什么差别吗?
vector<int> avoidFlood(vector<int>& rains) {
int n = rains.size();
vector<int> ans(n,1);
unordered_map<int,int> pool2last_rain;
set<int> sunny;
for(int idx = 0;idx < n;idx++){
if(rains[idx] == 0){
sunny.insert(idx);
continue;
}
if(pool2last_rain.count(rains[idx]) != 0){
int last_rain = pool2last_rain[rains[idx]];
auto last_sunny_it = lower_bound(sunny.begin(),sunny.end(),last_rain);
//auto last_sunny_it = sunny.lower_bound(last_rain);
if(last_sunny_it == sunny.end()) return {};
int last_sunny_day = *last_sunny_it;
sunny.erase(last_sunny_it);
ans[last_sunny_day] = rains[idx];
}
pool2last_rain[rains[idx]] = idx;
ans[idx] = -1;
}
return ans;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)