1488. Avoid Flood in The City

題目

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake that is full of water, there will be a flood. Your goal is to avoid floods in any lake.

Given an integer array rains where:

rains[i] > 0 means there will be rains over the rains[i] lake.
rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.

Return an array ans where:

ans.length == rains.length
ans[i] == -1 if rains[i] > 0.
ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.

If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.

Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes.

題目連結

輸入的 rains 陣列代表會下雨的湖的編號，0 代表不會下雨，如果同個湖下兩次雨就會淹水，如果沒下雨的話可以放乾一座湖 (也可以不放)，目標是要找到不會讓任何一座湖淹水的組合

思路

核心是陣列裡面出現重複的數字的時候就代表有湖會淹水，而且重複的組數要 <= 0 的數量，以及 0 出現的位置也需要考慮，否則會來不及放乾。所以在檢查的時候考慮幾種狀況：

### Case 1 - possible
rains = [1, 0, 2]
### Case 2 - possible
rains = [1, 0, 1, 2]
### Case 3 - impossible
rains = [1, 2, 0, 1, 2]
### Case 4 - impossible
rains = [1, 1, 0, 2]
### Case 5 - possible
rains = [1, 2, 0, 2, 3, 0, 1]

原本的想法是想要一邊遍歷 rains 一邊判斷、處理結果，用一個 stack 維護目前滿水的湖，和一個 array 紀錄動作，分成兩個狀況：

有下雨 -> 看 stack 裡有沒有相同的編號，如果有代表會淹水直接回傳空陣列，沒有的話就把編號放到 stack 裡面，array 紀錄 -1
沒下雨 -> 看 stack 裡有沒有東西，如果有的話就把它 pop 出來然後記錄到 array 裡。stack 是空的話就紀錄 1 進去 (隨便放乾一個空的湖)

但因為 Case 5 的狀況導致直接這樣做會有點困難，因為不知道後面哪個湖會下雨，因此在第六輪不能決策出要放乾哪個湖。所以想法變成遇到不下雨的時候不直接先放乾，而是等到遇到會淹水的狀況時再處理，會用三個資料結構來維護：

lakeRecord：一個 dict 記錄每個湖最後下雨的日子，也就是該元素在陣列中的 index
actionList：一個 list 記錄每一輪的動作，也是最後要回傳的結果
zeroIdxs：一個 list 記錄陣列中 0 的 indx，代表可以放乾湖的日子

每一輪的處理變成：

沒下雨 -> actionList 先填 1 代表隨便放乾空湖，然後把 index 記錄到 zeroIdxs 裡面

def recordZero(self, zeroIdx):
    self.actionList.append(1)
    self.zeroIdxs.append(zeroIdx)

有下雨 -> actionList 記錄 -1，如果這個湖已經滿了 (在 lakeRecord 有記錄)，從 zeroIdxs 裡面搜索是否有可以放乾該湖的日子 (意思是 0 要夾在兩個下雨天之間)：

def searchZeroBetween(self, start, end):
    if len(self.zeroIdxs) == 0:
        return -1

    for zeroIdx in self.zeroIdxs:
        if zeroIdx <= end and zeroIdx >= start:
            return zeroIdx

    return -1

如果找不到代表沒辦法解決水災可以直接回傳空陣列，如果可以的話就把找到的日子指定給這個湖放乾，並且把日子從 zeroIdxs 中移除。遍歷完輸入的 rains 陣列後即完成。

Full Code

class Solution:
    def __init__(self):
        self.lakeRecord = {}
        self.actionList = []
        self.zeroIdxs = []

    # 沒下雨 -> actionList 先記錄 1，然後把 0 的 idx 記錄下來
    def recordZero(self, zeroIdx):
        self.actionList.append(1)
        self.zeroIdxs.append(zeroIdx)

    # 尋找是否有可以放乾湖的一天
    def searchZeroBetween(self, start, end):
        if len(self.zeroIdxs) == 0:
            return -1

        for zeroIdx in self.zeroIdxs:
            if zeroIdx <= end and zeroIdx >= start:
                return zeroIdx

        return -1
        
    def avoidFlood(self, rains: List[int]) -> List[int]:
        for day, action in enumerate(rains):
            # 沒下雨
            if action == 0:
                self.recordZero(day)
            # 有下雨
            else:
                self.actionList.append(-1)
                # 如果下雨的湖已經滿了，需要去尋找有哪天可以放乾
                if action in self.lakeRecord.keys():
                    dryDay = self.searchZeroBetween(self.lakeRecord[action], day)

                    # 找不到可以放乾的日子
                    if dryDay == -1:
                        return []
                    # 有找到，指定該天給這個湖，然後從 zeroIdxs 移除掉這天
                    else:
                        self.actionList[dryDay] = action
                        self.zeroIdxs.remove(dryDay)
                self.lakeRecord[action] = day

        return self.actionList