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

概述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 t

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..<m12         {13             for j in 0..<n14             {15                 if i == 0 || i == m - 1 || j == 0 || j == n - 116                 {17                     q.append([heightmap[i][j],i * n + j])18                     visited[i][j] = true19                 }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] / n28             var c:Int = t[1] % n29             mx = max(mx,h)30             for i in 0..<dir.count31             {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                     continue37                 }38                 visited[x][y] = true39                 if heightmap[x][y] < mx40                 {41                     res += mx - heightmap[x][y]42                 }43                 q.append([heightmap[x][y],x * n + y])44             }45         }46         return res47     }48 }