Leetcode—1488.避免洪水泛滥【中等】

本文主要是介绍Leetcode—1488.避免洪水泛滥【中等】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2023每日刷题（十四）

Leetcode—1488.避免洪水泛滥

算法思想

• 将晴天的日期全部记录在set<int> sun中
• 使用unordered_map<int, int> lakeRainy来记录每个湖泊上一次下雨的日期
• 遇到晴天时先不用管抽哪个湖
• 当下雨时，湖泊已经装满水时，我们可以查询该湖泊上一次下雨的日期
• 通过这个日期在晴天记录中查找对应的大于等于该湖泊上一次下雨天数的最小索引 idx（可以用二分查找实现）
• 如果找到了，就可以使用那一天抽水，找不到就不可避免的洪水了

实现代码

class Solution {
public:vector<int> avoidFlood(vector<int>& rains) {int n = rains.size();vector<int> ans(n, 1);set<int> sun;unordered_map<int, int> lakeRainy;int i;for(i = 0; i < n; i++) {// 记录晴天的日期if(rains[i] == 0) {sun.insert(i);continue;}if(lakeRainy.count(rains[i]) != 0) {auto t = sun.lower_bound(lakeRainy[rains[i]]);if(t == sun.end()) {return {};}ans[*t] = rains[i];sun.erase(t);}ans[i] = -1;lakeRainy[rains[i]] = i;}return ans;}
};

运行结果

之后我会持续更新，如果喜欢我的文章，请记得一键三连哦，点赞关注收藏，你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 ！！！↖(▔▽▔)↗感谢支持！

这篇关于Leetcode—1488.避免洪水泛滥【中等】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---