接雨水 II

407. 接雨水 II (Hard)

给你一个 m x n 的矩阵,其中的值均为非负整数,代表二维高度图每个单元的高度,请计算图中形状最多能接多少体积的雨水。

 

示例:

给出如下 3x6 的高度图:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

返回 4 。

如上图所示,这是下雨前的高度图[[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 的状态。

 

下雨后,雨水将会被存储在这些方块中。总的接雨水量是4。

 

提示:

  • 1 <= m, n <= 110
  • 0 <= heightMap[i][j] <= 20000

相关话题

[] [广度优先搜索]

相似题目

  1. 接雨水 (Hard)

解法