407. Trapping Rain Water II

Leetcode link

题目简介

本题是一道困难题，题目只给我们一个参数 heightMap 代表一个有 m*n 个格子的矩阵，每个矩阵上有 heightMap[m][n] 个格子

题目要我们求如果下雨的话，这个矩阵上面的格子最多能留下多少格的雨水

解题思路

这题我们需要先从格子的边缘开始寻找思路

我们知道一个桶最多能接多少水取决于桶子的短板，所以我们第一步要先找到矩阵边缘最低的格子，然后将其与相邻的格子对比高度：

• 如果相邻格子比边缘最低的格子低，那么相邻格子就可以留下 边缘最低格子高度 - 相邻格子高度 的水
• 如果相邻格子比边缘最低的格子高，那么我们就再找到边缘第二低的格子……以此类推

换成算法的思路的话，我们要重复如下步骤：

1. 创建一个与 heightMap 大小相同的数组 visited 来保存已经访问过的位置
2. 创建一个小顶堆 minHeap 并且将所有的边缘格子放进其中，将 visited 数组中边缘格子的位置设置为 true 表示已经访问过了（因为边缘的格子之间已经在小顶堆中比较过了，不需要加入相邻的比较中）
3. 取出 minHeap 的堆顶元素，将其与相邻且还没访问过的格子比较
4. 如果当前格子比相邻格子高，把高度加到结果 res 中，然后将当前相邻格子加到 minHeap 中，并且相邻格子的高度要取当前格子与相邻格子中较高的高度
5. 如果当前格子比相邻格子低，则跳过
6. 重复步骤 3，直到 minHeap 为空
7. 返回结果 res

Javascript

/**
 * @param {number[][]} heightMap
 * @return {number}
 */
var trapRainWater = function (heightMap) {
    const len = heightMap.length
    const width = heightMap[0].length
    const visited = new Array(len).fill().map(item => new Array(width).fill(false))
    // [height, x, y]
    const minHeap = new PriorityQueue((a, b) => a[0] - b[0])

    // push all the edge to the minHeap and mark visited as true
    for (let i = 0; i < len; i++) {
        minHeap.enqueue([heightMap[i][0], i, 0])
        visited[i][0] = true
        minHeap.enqueue([heightMap[i][width - 1], i, width - 1])
        visited[i][width - 1] = true
    }
    for (let j = 1; j < width - 1; j++) {
        minHeap.enqueue([heightMap[0][j], 0, j])
        visited[0][j] = true
        minHeap.enqueue([heightMap[len - 1][j], len - 1, j])
        visited[len - 1][j] = true
    }

    let res = 0
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    while (!minHeap.isEmpty()) {
        const [height, x, y] = minHeap.dequeue()

        for (const dir of directions) {
            const nx = x + dir[0]
            const ny = y + dir[1]

            if (nx >= 0 && nx < len && ny >= 0 && ny < width && !visited[nx][ny]) {
                res += Math.max(0, height - heightMap[nx][ny])
                minHeap.enqueue([Math.max(height, heightMap[nx][ny]), nx, ny])
                visited[nx][ny] = true
            }
        }
    }

    return res
};