LeetCode 407. Trapping Rain Water II

LeetCode 407. Trapping Rain Water II

Description

Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note:

Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

Given the following 3×6 height map:
[
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1]
]

Return 4.

The above image represents the elevation map [1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1] before the rain.

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

思路

  • 这道题虽然叫 Trapping Rain Water II,但是题目的解法和 Trapping Rain Water 并不一样。
  • 这道题用到的基本数据结构是小顶堆。
  • 基本思路是:我们想象海平面的海水慢慢侵入方格,依次找到会被海水填满的格子。
  • 我们把最外面的四边当成四面墙,想象海水面不断的升高,首先会浸过墙面最低的格子,如果墙面最低格子的四周(出了在墙面的格子)有比它矮的格子,那么这就可以形成一个蓄水池,蓄水池的最高高度就是墙面最低的格子,于是我们计算这个蓄水池可以获得的蓄水量;然后这个蓄水池被添加到墙面中;继续在墙面中找最低的格子;
  • 这个视频的动画解释的非常清楚
# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-10-03 08:11:17
# @Last Modified by:   何睿
# @Last Modified time: 2019-10-03 11:57:48

import heapq

from typing import List


class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        if not heightMap or not heightMap[0]:
            return 0
        queue, visited, max_heigth, water = [], set(), 0, 0
        row, col = len(heightMap), len(heightMap[0])
        count = row * col

        self.fill_border(queue, heightMap)
        visited = {(row, col) for _, row, col in queue}
        while queue:
            # 当所有的格子都在墙面上时,结束
            if len(visited) == count:
                return water
            height, i, j = heapq.heappop(queue)
            max_heigth = max(max_heigth, height)
            # 以最低的格子为起点,判断四周是否可以形成蓄水池,返回蓄水池蓄水的大小
            water += self.visit_neighbors(queue, visited, heightMap, max_heigth, row, col, i, j)
        return water

    def visit_neighbors(self, queue, visited, heightMap, max_heigth, row, col, i, j):

        water = 0
        for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nrow, ncol = i + x, j + y
            if (nrow, ncol) not in visited and self.is_in_border(row, col, nrow, ncol):
                num = heightMap[nrow][ncol]
                water += max(0, max_heigth - num)
                visited.add((nrow, ncol))
                heapq.heappush(queue, (num, nrow, ncol))

        return water

    def fill_border(self, queue, heightMap):
        row, col = len(heightMap), len(heightMap[0])
        for i in range(row):
            heapq.heappush(queue, (heightMap[i][0], i, 0))
            heapq.heappush(queue, (heightMap[i][-1], i, col - 1))
        for i in range(1, col - 1):
            heapq.heappush(queue, (heightMap[0][i], 0, i))
            heapq.heappush(queue, (heightMap[-1][i], row - 1, i))

    def is_in_border(self, row, col, i, j):
        return 0 <= i < row and 0 <= j < col

源代码文件在 这里 。


©本文是原创文章,欢迎转载,转载需保留 文章来源 ,作者信息和本声明.

Posted in 力扣 and tagged , .

花若盛開,蝴蝶自來. 分享学习,每天进步一点点

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据