leetcode每日一题—407.接雨水II

wuchangjian2021-11-03 21:24:53编程学习

题目:
给你一个 m x n 的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
思路:
水桶原理:一只水桶能装多少水, 完全取决于它最短的那块木板。

解答:

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        #只有两行或两列
        if m <= 2 or n <= 2:
            return 0

        visited = [[0 for _ in range(n)] for _ in range(m)]
        pq = []    #小根堆
        for i in range(m):
            for j in range(n):
                #若位于边界
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    visited[i][j] = 1
                    heapq.heappush(pq, (heightMap[i][j], i * n + j))
        
        res = 0
        #通过四次循环,由dir[i]和dir[i+1]确定四个走向【上,右,下,左】
        dirs = [-1, 0, 1, 0, -1]
        while pq:
            #确保从最小的方块开始行走
            height, position = heapq.heappop(pq)
            for k in range(4):
                nx, ny = position // n + dirs[k], position % n + dirs[k + 1]
                #如果位于中间位置且未访问过
                if nx >= 0 and nx < m and ny >= 0 and ny < n and visited[nx][ny] == 0:
                    if height > heightMap[nx][ny]:
                        res += height - heightMap[nx][ny]
                    visited[nx][ny] = 1    
                    heapq.heappush(pq, (max(height, heightMap[nx][ny]), nx * n + ny))
        return res


相关文章

<input>标签构建快递信息界面(HTML+CSS)

效果显示 HTML代码  <!doctype html> <h...

Hadoop搭建的顺序(/usr/local/src)

一:配置VM中的网络环境 1.以管理员形式运行VMware 2.打开虚拟网...

机器人游戏

【问题描述】        有人建造了一些机器人,并且将他们放置在包含n...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。