2023每日刷題（十四）

Leetcode—1488.避免洪水泛濫

算法思想

• 將晴天的日期全部記錄在set<int> sun中
• 使用unordered_map<int, int> lakeRainy來記錄每個(gè)湖泊上一次下雨的日期
• 遇到晴天時(shí)先不用管抽哪個(gè)湖
• 當(dāng)下雨時(shí)，湖泊已經(jīng)裝滿水時(shí)，我們可以查詢該湖泊上一次下雨的日期
• 通過這個(gè)日期在晴天記錄中查找對應(yīng)的大于等于該湖泊上一次下雨天數(shù)的最小索引?idx（可以用二分查找實(shí)現(xiàn)）
• 如果找到了，就可以使用那一天抽水，找不到就不可避免的洪水了

實(shí)現(xiàn)代碼

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;}
};

運(yùn)行結(jié)果

之后我會(huì)持續(xù)更新，如果喜歡我的文章，請記得一鍵三連哦，點(diǎn)贊關(guān)注收藏，你的每一個(gè)贊每一份關(guān)注每一次收藏都將是我前進(jìn)路上的無限動(dòng)力 ！！！↖(▔▽▔)↗感謝支持！