1. 題目

你的國家有無數個湖泊，所有湖泊一開始都是空的。
當第 n 個湖泊下雨的時候，如果第 n 個湖泊是空的，那么它就會裝滿水，否則這個湖泊會發生洪水。
你的目標是避免任意一個湖泊發生洪水。

給你一個整數數組 rains ，其中：

• rains[i] > 0 表示第 i 天時，第 rains[i] 個湖泊會下雨。
• rains[i] == 0 表示第 i 天沒有湖泊會下雨，你可以選擇 一個 湖泊并 抽干 這個湖泊的水。

請返回一個數組 ans ，滿足：

• ans.length == rains.length
• 如果 rains[i] > 0 ，那么ans[i] == -1 。
• 如果 rains[i] == 0 ，ans[i] 是你第 i 天選擇抽干的湖泊。

如果有多種可行解，請返回它們中的 任意一個 。
如果沒辦法阻止洪水，請返回一個 空的數組 。

請注意，如果你選擇抽干一個裝滿水的湖泊，它會變成一個空的湖泊。但如果你選擇抽干一個空的湖泊，那么將無事發生（詳情請看示例 4）。

示例 1： 輸入：rains = [1,2,3,4] 輸出：[-1,-1,-1,-1] 解釋：第一天后，裝滿水的湖泊包括 [1] 第二天后，裝滿水的湖泊包括 [1,2] 第三天后，裝滿水的湖泊包括 [1,2,3] 第四天后，裝滿水的湖泊包括 [1,2,3,4] 沒有哪一天你可以抽干任何湖泊的水，也沒有湖泊會發生洪水。示例 2： 輸入：rains = [1,2,0,0,2,1] 輸出：[-1,-1,2,1,-1,-1] 解釋：第一天后，裝滿水的湖泊包括 [1] 第二天后，裝滿水的湖泊包括 [1,2] 第三天后，我們抽干湖泊 2 。所以剩下裝滿水的湖泊包括 [1] 第四天后，我們抽干湖泊 1 。所以暫時沒有裝滿水的湖泊了。 第五天后，裝滿水的湖泊包括 [2]。 第六天后，裝滿水的湖泊包括 [1,2]。 可以看出，這個方案下不會有洪水發生。 同時， [-1,-1,1,2,-1,-1] 也是另一個可行的沒有洪水的方案。示例 3： 輸入：rains = [1,2,0,1,2] 輸出：[] 解釋：第二天后，裝滿水的湖泊包括 [1,2]。 我們可以在第三天抽干一個湖泊的水。 但第三天后，湖泊 1 和 2 都會再次下雨， 所以不管我們第三天抽干哪個湖泊的水，另一個湖泊都會發生洪水。示例 4： 輸入：rains = [69,0,0,0,69] 輸出：[-1,69,1,1,-1] 解釋：任何形如 [-1,69,x,y,-1], [-1,x,69,y,-1] 或者 [-1,x,y,69,-1] 都是可行的解，其中 1 <= x,y <= 10^9示例 5： 輸入：rains = [10,20,20] 輸出：[] 解釋：由于湖泊 20 會連續下 2 天的雨，所以沒有沒有辦法阻止洪水。提示： 1 <= rains.length <= 10^5 0 <= rains[i] <= 10^9

2. 解題

• 找到要抽水的湖往后的最近的一天抽水

set 二分查找

class Solution { public:vector<int> avoidFlood(vector<int>& rains) {vector<int> ans(rains.size(), -1);unordered_map<int,int> laker;//要抽水的湖泊數字, 對應的天idxset<int> s;for(int i = 0; i < rains.size(); ++i){if(rains[i])//打雷了，下雨了，rains[i]號填滿了{if(laker.find(rains[i]) == laker.end())laker[rains[i]] = i;else//今天要下雨，這個湖有水，危險，我們要找之前的一天抽水{auto it = s.lower_bound(laker[rains[i]]);//找到下雨后續的抽水天if(it == s.end())//沒找打return {};ans[*it] = rains[i];//后續的那天抽水laker[rains[i]] = i;//更新當前的天數s.erase(it);//抽完水了，刪除}}else//沒有下雨，可以抽水s.insert(i);}for(auto it = s.begin(); it != s.end(); ++it)ans[*it] = 1;//剩余的可抽水天填任意值return ans;} };

696 ms 109.6 MB

總結

以上是生活随笔為你收集整理的LeetCode 1488. 避免洪水泛滥（贪心+set二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。