[LeetCode] 407. Trapping Rain Water II @ python

本文主要是介绍[LeetCode] 407. Trapping Rain Water II @ python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一．题目：
给定一个m x n的矩阵，其中的值均为正整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。

二．解题思路：
要想知道每个位置的盛水量，我们需要计算它的四邻域高度的最小值．另外，注意到里面位置的盛水量和外围的高度值有关系，所以我们可以从边界开始一层一层往里计算，使用广度优先搜索不断更新每个位置的高度值．
代码如下：

class Solution(object):def trapRainWater(self, heightMap):""":type heightMap: List[List[int]]:rtype: int"""if heightMap == []:return 0m = len(heightMap)n = len(heightMap[0])peakMap = [[float("inf")]*n for __ in range(m)]stack = []for i in range(m):for j in range(n):if i in (0,m-1) or j in (0,n-1):peakMap[i][j] = heightMap[i][j]stack.append((i,j))#从外到内，一层一层更新peakMap.peakMap每一层上某个位置的数值表示max(min(上一层上邻近该位置的数值),当前位置的实际高度)while stack:i,j = stack.pop(0)dirs = [(0,1),(0,-1),(1,0),(-1,0)]for dx,dy in dirs:nx,ny = i+dx,j+dyif nx <0 or nx >m-1 or ny<0 or ny > n-1:continuelimit = max(peakMap[i][j], heightMap[nx][ny])if peakMap[nx][ny] > limit:peakMap[nx][ny] = limitstack.append((nx,ny))return sum([peakMap[i][j] - heightMap[i][j] for i in range(m) for j in range(n)])

这篇关于[LeetCode] 407. Trapping Rain Water II @ python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---