二维数组中的总水容量,表示地形图

我最近在一次采访中被问到这个问题,我不知道如何实现它。我希望有人能给我指出解决这个问题的正确方向。

问题陈述:给定一个二维整数数组,找出可以容纳的总水量。数字表示地图中的海拔高度(即山的高度)。水从最高的山流向山谷(从最高到最低)。

例1:这是 5 x 3 矩阵。10是最高峰。你可以假设水向下流动,并开始在第2块地砖处收集,该地砖处于坐标位置 (3, 1) . 此磁贴将收集 水的单位。在以坐标方向溢出到相邻高度为9的瓷砖之前 (2, 0) or (3, 0) 流入海洋(假设边缘被海洋包围)。所以为这张地图收集的水总量是 .

9  9  9
9 10  9
9  9  9
9  2  10
10 10 10

    9   9  9  9  9 9
    9  10  9  8  2 4
    9   9  9 10  3 5
    9   2  2 10  3 5
   10 10  10 10  9 9

在这种情况下,水可以按以下坐标收集:

1. (3,1)和(3,2)。所以总容量=>7+7=14
2. (1,4)(2,4)和(3,4)。这些坐标可以分别存储2、1、1。因为在水开始以坐标(1,5)从边缘溢出之前,它们能容纳的最大值是4。所以总容量=>2+1+1=4

总容量为14+4=18。