1488. Avoid Flood in The City

Leetcode link

解题思路

本题的关键在于我们要怎么在同一个湖的下一场雨之前把湖水排干

为了这个目的我们需要提前做一些准备：

• fullLakes：一个 Map，用来保存 rains[i], i，记录之前的雨下在 rains[i] 湖的下标（日期）

• dryDays：数组，用来记录还未使用的没下雨的下标（日期），这样可以在将来下雨的时候用

• res：数组，用来保存答案

有了这些之后，我们的算法步骤如下：

1. 遍历 rain 数组

2. 如果当天没下雨，则将当前下标保存到 dryDays 中，然后回到步骤 1

3. 如果当天下雨了，判断当前下雨的湖泊之前是否有下过雨（是否在 fullLakes 中），如果有则在 dryDays 中寻找从上次下雨到现在范围内最早的 dryDay 放水；如果没有就把当前下雨的湖泊记录到 fullLakes 中
4. 如果在 dryDays 中找不到符合规则的时间，则返回空数组 []

题目描述有一点没有说清楚，如果当天没下雨，但是也没有需要放水的湖泊了，我们仍然需要选择一个 1～无限大的数字来填充进数组

不然这个 case 就会失败：

// testcase
[69,0,0,0,69]

// expect
[-1,69,1,1,-1]

下标 2、3 的数字不能是 -1。。。所以我们一开始给数组 res 要默认赋值 1

Javascript

/**
 * @param {number[]} rains
 * @return {number[]}
 */
var avoidFlood = function (rains) {
    const res = new Array(rains.length).fill(1)
    // {rains[i], i}
    const fullLakes = new Map()
    const dryDays = []

    for (let i = 0; i < rains.length; i++) {
        if (rains[i] === 0) {
            dryDays.push(i)
        } else {
            res[i] = -1
            if (fullLakes.has(rains[i])) {
                const idx = binarySearch(dryDays, fullLakes.get(rains[i]))
                if (idx === dryDays.length) {
                    return []
                }
                res[dryDays[idx]] = rains[i]
                const dryIdx = dryDays.splice(idx, 1)
            }
            fullLakes.set(rains[i], i)
        }
    }
    return res
};

const binarySearch = (arr, target) => {
    let left = 0
    let right = arr.length

    while (left < right) {
        let mid = (left + right) >> 1
        if (arr[mid] <= target) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}