[Swift]LeetCode407. 接雨水 II | Trapping Rain Water II

发布时间：2020-12-14 05:05:20 所属栏目：百科来源：网络整理

导读：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 c

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 3x6 height map:
[
  [1,4,3,1,2],[3,2,4],[2,1]
]

Return 4.

The above image represents the elevation map?[[1,1]]?before the rain.?

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

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

说明:

m?和?n?都是小于110的整数。每一个单位的高度都大于0 且小于 20000。?

示例：

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

返回 4。

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

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

超出时间限制

 1 class Solution {
 2     func trapRainWater(_ heightMap: [[Int]]) -> Int {
 3         if heightMap.isEmpty {return 0}
 4         var m:Int = heightMap.count
 5         var n:Int = heightMap[0].count
 6         var res:Int = 0
 7         var mx:Int = Int.min
 8         var q:[[Int]] = [[Int]]()
 9         var visited:[[Bool]] = [[Bool]](repeating:[Bool](repeating:false,count:n),count:m)
10         var dir:[[Int]] = [[0,-1],[-1,0],[0,1],[1,0]]
11         for i in 0..<m
12         {
13             for j in 0..<n
14             {
15                 if i == 0 || i == m - 1 || j == 0 || j == n - 1
16                 {
17                     q.append([heightMap[i][j],i * n + j])
18                     visited[i][j] = true
19                 }
20             }
21         }
22         while(!q.isEmpty)
23         {
24             q = q.sorted { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] > $1[0] }
25             var t:[Int] = q.removeLast()           
26             var h:Int = t[0]
27             var r:Int = t[1] / n
28             var c:Int = t[1] % n
29             mx = max(mx,h)
30             for i in 0..<dir.count
31             {
32                 var x:Int = r + dir[i][0]
33                 var y:Int = c + dir[i][1]
34                 if x < 0 || x >= m || y < 0 || y >= n || visited[x][y]
35                 {
36                     continue
37                 }
38                 visited[x][y] = true
39                 if heightMap[x][y] < mx
40                 {
41                     res += mx - heightMap[x][y]
42                 }
43                 q.append([heightMap[x][y],x * n + y])
44             }
45         }
46         return res
47     }
48 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!