LeetCode 807 求保持城市现有天际线的最大增高

1 题目描述

在二维数组grid中,每个值grid[i][j]代表位于此的建筑物高度。我们允许对其中的任意建筑物增长不等的高度。高度0仍为一个有效的建筑物。 增高后的建筑群,从其四个方向来看,必须与之前建筑群的天际线保持一致。城市天际线是从远处观看时,由所有建筑组成的外形轮廓。请看如下例子。

请计算所有建筑物可以增长的最大总和。

例子:

输入:

grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]

输出:35

释义:

二维矩阵为:
[ 
[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] 
]

总增长为35。

题目出处:LeetCode

2 解决思路

欲保持天际线不变,对于每个建筑来说,其最大高度为其所在行最高与所在列最高的较小值。

所以如下算法,先遍历一遍矩阵,计算出行最高数组与列最高数组。

然后再遍历一遍矩阵,根据如上两个数组计算各个建筑的最大可增长高度,最后返回总增加高度。

3 Golang实现代码

https://github.com/olzhy/

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func maxIncreaseKeepingSkyline(grid [][]int) int {
    rowMaxs := make([]int, len(grid))
    colMaxs := make([]int, len(grid[0]))
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            e := grid[i][j]
            if e > rowMaxs[i] {
                rowMaxs[i] = e
            }
            if e > colMaxs[j] {
                colMaxs[j] = e
            }
        }
    }
    increments := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[0]); j++ {
            e := grid[i][j]
            increments += (min(rowMaxs[i], colMaxs[j]) - e)
        }
    }
    return increments
}
若觉得文章对您有所帮助,可以请我喝杯咖啡,Thanks!
微信 支付宝