[Swift]LeetCode807.保持城市天际线|MaxIncreasetoKeepCitySkyline

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10550115.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

In a 2 dimensional array grid, each value grid[i][j]represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well.

At the end, the "skyline" when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city's skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.

What is the maximum total sum that the height of the buildings can be increased?

Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: 
The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

Notes:

1 < grid.length = grid[0].length <= 50.
All heights grid[i][j] are in the range [0, 100].
All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j]rectangular prism.

在二维数组grid中，grid[i][j]代表位于某处的建筑物的高度。我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。高度 0 也被认为是建筑物。

最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。请看下面的例子。

建筑物高度可以增加的最大总和是多少？

例子：
输入： grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出： 35
解释： 
The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

从数组竖直方向（即顶部，底部）看“天际线”是：[9, 4, 8, 7]
从水平水平方向（即左侧，右侧）看“天际线”是：[8, 7, 9, 3]

在不影响天际线的情况下对建筑物进行增高后，新数组如下：

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

说明:

1 < grid.length = grid[0].length <= 50。
grid[i][j] 的高度范围是： [0, 100]。
一座建筑物占据一个grid[i][j]：换言之，它们是 1 x 1 x grid[i][j] 的长方体。

Runtime: 44 ms

Memory Usage: 18.4 MB

 1 class Solution {
 2     func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {        
 3         if grid.count <= 1 {
 4             return 0
 5         }
 6         
 7         let count = grid.count
 8         
 9         var hHeight:[Int] = Array(repeating: 0 , count: count)
10         var vHeight:[Int] = Array(repeating: 0 , count: count)        
11         
12         var height : Int = 0
13         
14         for hIdx in 0..<count{
15             for vIdx in 0..<count {
16                 height = grid[hIdx][vIdx]
17                 if height > hHeight[hIdx] {
18                     hHeight[hIdx] = height
19                 }
20                 if height > vHeight[vIdx] {
21                     vHeight[vIdx] = height
22                 }
23             }
24         }        
25 
26         var gridOffsetCount:Int = 0
27         var maxGrid : Int = 0
28         for vIdx in 0..<count{
29             for hIdx in 0..<count {
30                 maxGrid = min(vHeight[vIdx] , hHeight[hIdx])
31                 height = grid[hIdx][vIdx]
32                 if maxGrid > height{
33                     gridOffsetCount += maxGrid - height
34                 }                
35             }
36         }        
37         return gridOffsetCount
38     }
39 }

44ms

 1 class Solution {
 2     func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {
 3         let side = grid.compactMap{ $0.max() }
 4         let top = getTopSkyline(for: grid)
 5         
 6         guard grid.count > 0,
 7             top.count == side.count else {
 8                 // invalid grid input
 9                 return 0
10             }
11         
12         let increase = computeMaxIncrease(for: grid, top: top, side:side)
13         return increase
14     }
15     
16     private func computeMaxIncrease(for grid:[[Int]], top: [Int], side:[Int]) -> Int {
17         var increase = 0
18         for i in 0..<top.count {
19             for j in 0..<side.count {
20                 let topMax = top[i]
21                 let sideMax = side[j]
22                 let highest = min(top[i], side[j])
23                 
24                 increase += highest - grid[i][j]
25             }
26         }
27         
28         return increase
29     }
30     
31     private func getTopSkyline(for grid:[[Int]]) -> [Int] {
32         var top = [Int]()
33         let length = grid.count
34         for i in 0..<length {
35             var maxValue = -1
36 
37             for j in 0..<length {
38                 maxValue = max(grid[j][i], maxValue)
39             }
40             top.append(maxValue)
41         }
42         
43         return top
44     }
45 }

Runtime: 48 ms

Memory Usage: 19.1 MB

 1 class Solution {
 2     func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {
 3         var m:Int = grid.count
 4         var n:Int = grid[0].count
 5         var res:Int = 0
 6         var row:[Int] = [Int](repeating:0,count:m)
 7         var col:[Int] = [Int](repeating:0,count:n)
 8         for i in 0..<m
 9         {
10             for j in 0..<n
11             {
12                 row[i] = max(row[i], grid[i][j])
13                 col[j] = max(col[j], grid[i][j])
14             }
15         }
16         for i in 0..<m
17         {
18             for j in 0..<n
19             {
20                 res += min(row[i] - grid[i][j], col[j] - grid[i][j])
21             }
22         }
23         return res
24     }
25 }

48ms

 1 class Solution {
 2     func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {
 3         let maxRow = grid.map { $0.max()! }
 4         let maxCol = getMaxCol(grid)
 5         let length = grid.count
 6         var out = 0
 7         
 8         for i in 0..<length {
 9             for j in 0..<length {
10                 let increase = min(maxRow[i], maxCol[j])
11                 let diff = increase - grid[i][j]
12                 out += diff
13             }
14         }
15         
16         return out
17         
18     }
19 
20     func getMaxCol(_ grid: [[Int]]) -> [Int] {
21         var out = [Int]()
22         for column in 0 ..< grid.count {
23             out.append(grid.map { $0[ column ] }.max()!)
24         }
25         return out
26     }
27 }

52ms

 1 class Solution {
 2     func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {
 3         let row_max = grid.map { $0.max()! }
 4         let col_max = (0..<grid[0].count).map { i in grid.map { $0[i] }.max()! }
 5         var count = 0
 6         for (i, row) in grid.enumerated() {
 7             for (j, el) in row.enumerated() {
 8                 count += min(row_max[i], col_max[j]) - el
 9             }
10         }
11         return count
12     }
13 }

56ms

 1 class Solution {
 2     func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {
 3         let row_maxes = grid.map { $0.max()! }
 4         let col_maxes = (0..<grid[0].count)
 5             .map { i in grid.reduce(0, { prev, next -> Int in max(prev, next[i]) }) }
 6 
 7         return zip(row_maxes, grid)
 8             .map { row_max, row in zip(col_maxes, row)
 9             .reduce(0, { prev, vals -> Int in prev + min(row_max, vals.0) - vals.1 }) }
10             .reduce(0, +)
11     }
12 }

64ms

 1 class Solution {
 2     func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {
 3         var result : Int = 0
 4         var rowMax :[Int] = []
 5         var colMax :[Int] = []
 6         for i in 0 ..< grid.count {
 7             rowMax.append(grid[i].max()!)
 8             colMax.append(grid.map{ $0[i] }.max()!)
 9         }
10         
11         for i in 0 ..< grid.count {
12             for j in 0 ..< grid.count {
13                 result += min(rowMax[i],colMax[j]) - grid[i][j]
14             }
15         }
16         return result
17     }
18 }

72ms

 1 class Solution {
 2     func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {
 3     let rowsMaxes = grid.map { $0.max() ?? 0 }
 4     let columnsMaxes = getVerticalView(of: grid).map { $0.max() ?? 0 }
 5     
 6     return grid.enumerated().map { (arg) -> Int in
 7         
 8         let (i, _) = arg
 9         return grid[i].enumerated().map { (j, _) -> Int in
10             let newTotal = min(rowsMaxes[i], columnsMaxes[j])
11             return newTotal - grid[i][j]
12         }.reduce(0, +)
13     }.reduce(0, +)
14 }
15 
16 fileprivate func getVerticalView(of grid: [[Int]]) -> [[Int]] {
17     return (0..<grid[0].count).map { index -> [Int] in
18         return grid.map { $0[index] }
19     }
20   } 
21 }

76ms

 1 class Solution {
 2     func maxIncreaseKeepingSkyline(_ grid: [[Int]]) -> Int {
 3         var horizontalSkyline = [Int:Int]()
 4         var verticalSkyline = [Int:Int]()
 5         for (hIndex, row) in grid.enumerated() {
 6             var skyline = 0
 7             for (vIndex, element) in row.enumerated() {
 8                 skyline = max(skyline, element)
 9                 verticalSkyline[vIndex] = max(verticalSkyline[vIndex] ?? 0, element)
10             }
11             horizontalSkyline[hIndex] = skyline 
12         }
13         var sum = 0
14         for (hIndex, row) in grid.enumerated() {
15             for (vIndex, element) in row.enumerated() {
16                 sum += min(verticalSkyline[vIndex] ?? 0, horizontalSkyline[hIndex] ?? 0) - element
17             }
18         }
19         return sum
20     }
21 }