主題
題目連結：
題目意譯：
你的國家裡有著無限數量的湖泊。一開始，所有湖泊都是空的，但只要雨一旦下在第 n 座湖泊，該湖泊便會裝滿了水。而如果雨是下在裝滿水的湖泊，它將會氾濫。你的目標是避免掉任何氾濫發生。
給定一個整數陣列 rains，其中：
rains[i] > 0 代表著雨水會降在第 rains[i] 座湖泊。
rains[i] == 0 代表著這天沒有任何降雨，而你可以在這天中選擇任一湖泊來使其乾涸。
回傳一個陣列 ans，其中
ans.length == rains.length；
如果 rains[i] > 0，則 ans[i] == -1；
如果 rains[i] == 0，則 ans[i] 為你在第 i 天選擇使其乾涸的湖泊。
如果有多組可能的答案則回傳任意一個。如果不可能避免掉所有氾濫，則回傳一個空陣列。
注意到如果你選擇一個滿水的湖泊來使其乾涸，則它將會變成空的湖泊；但如果你選擇一個空的湖泊來使其乾涸，則沒有任何事情會發生。
限制：
1 ≦ rains.length ≦ 10 ^ 5
0 ≦ rains[i] ≦ 10 ^ 9
範例測資：
範例 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] 這些湖泊上。很簡單就可以看出無論你在第三天選擇讓哪座湖泊乾涸，另一座必定會氾濫。
解題思維：
可以看到如果有某兩天是下在同一座湖泊，假設是第 i 天和第 j 天，則我們需要在第 i 天到第 j 天之間（即 rains[i] ～ rains[j]）找到某一天可以使該湖泊乾涸（也就是找到某個 k 使得 i < k < j 且 rains[k] == 0）並且該天沒有要讓其他湖泊乾涸。
而為了盡可能地避免氾濫（可以看做是「最小化」氾濫次數，只是我們的要求是要 0 次），這個 k 要盡可能地接近 i。而這個命題可以用反證法證明：
假設命題的策略不是最佳的。因此存在著另一個「最佳解」使得某個湖泊 rains[j] 挑到的 k 值不是最接近前一次降雨的那一天 i 之 k 值，令其值為 k'（可以看到 k < k'）。而我們實際上不知道 k 值是什麼（畢竟 i + 1 可能已經被其他湖泊搶走了），因此下列論述需要對於 k = i + 1 ～ k' - 1 都要掃過一次。
此時如果 k' 真的存在，則可以再分成兩種情形：
一，k 那一天沒有被其他湖泊佔據。則我們直接把 k' 改成 k 就符合命題了。
二，k 那一天被另一個湖泊 rains[j'] 用掉了（令其對應的前一次降雨的那一天為 i'）且 k < j'。可以看到 i' 必定小於 k（畢竟裝滿了水的湖泊才有使其乾涸的必要），而因為 k < k'，因而可推得 i' 也必定小於 k'。因此我們可以直接交換 rains[j] 和 rains[j'] 兩者的選擇即可符合命題。
如果對於 k = i + 1 ～ k' - 1 有找到上述一或二之情況，則命題之策略不會比假想最佳解糟；而如果對於這些 k 值都找不到，則代表 k' 實際上就是我們要的 k 值，因此最佳解中 rains[j] 挑的 k' 值即符合命題之策略。
（註：個人認為這邊敘述不夠精確，但也不知道從何改起。希望各路神人可以指點迷津。）
另一種情況是 k' 不存在，意即 rains[j] 在這個「最佳解」中將會氾濫。
可以看到 k 沒有被其他湖泊佔據的情況絕對不會發生，因為我們可以直接挑 k 來避免此次氾濫。而這牴觸了這個假想「最佳解」的條件（因為我們讓氾濫次數比「最佳」還低）。
所以一樣，存在某個佔據 k 值的湖泊 rains[j']（對應的前一天降雨一樣是 i'）。而同樣的論述可以重複於 j' < j 之情況，也就是說 k ～ j' 之間不會有其他沒有被佔據的天數。因為如果存在則 rains[j'] 可以改挑那一天，而 rains[j] 就可以選 k 了（這將牴觸「最佳」之條件）。同樣地當 j < j' 時，j ～ j' 之間不會有某一天是沒有湖泊用的。
因此現在 rains[j] 就可以挑 k = i + 1 即可，所以會換某個 rains[j'] 氾濫，但是會符合命題之策略且氾濫數不變（註：我不確定會不會有可能變小，但至少這邊不影響結果）。
因故命題之策略無論如何都不會比假想最佳解糟。因此命題之策略實際上確實可得到最佳解。
也就是說我們需要把 rains[k] == 0 的這些 k 在掃過陣列 rains 時存起來，並且在遇到某個 rains[j] != 0 且先前存在另一天 rains[i] == rains[j]（這邊可以用一個雜湊表（Hash Table）來儲存每一座湖泊「最近一次」下雨的天數）的情況時，找到上述提及的 k 值並從中刪除該值（代表著用該天來使 rains[i] 這座湖泊乾涸）。
因此我們需要一個資料結構可以儲存這些索引值，並且單次搜尋（且其為搜尋「最接近」某個目標數字之種類）、刪除和插入的時間複雜度都應小於 O(n)（可寫為 o(n)），其中 n 為 rains 之長度。不然最糟時間複雜度會到 O(n ^ 2)。
而 C++ 中剛好有一個這樣子的資料結構——即「set」，其為一個稱為紅黑樹（Red-Black Tree）的自平衡二元搜尋樹（Self-Balancing Binary Search Tree）之資料結構。而其單次搜尋、刪除和插入的時間複雜度皆為 O(log n)。
（其他語言不熟，不知道有無對應之資料結構）
所以我們可以用 set 來依序加入每個 rains[k] == 0 時的 k 值，並在要氾濫時（即上述提及的 i 、 j 值）在這個 set 中來找到最接近 i 且大於 i 的 k 值並刪除該值（記得在陣列 ans 中記錄找到的 k 值）。只要找不到對應的 k 值就代表必定會氾濫，因此要直接回傳一個空陣列。反之如果掃完整個陣列 rains 都沒有出事的話，則回傳 ans。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
