力扣每日一题之保持城市天际线

发表于

给你一座nxn个街区组成的城市，每个截取都包含一座立方体建筑。给你一个坐标从0开始的nxn整数矩阵grid，其中grid[r][c]表示坐落于r行c列的建筑物的高度。

城市的天际线是从远处观察城市时，所有建筑物形成的外部轮廓。从东、南、西、北四个方向观测到的天际线可能不同。

我们被允许为任意数量的建筑物的高度增加任意增量（不同的建筑物的增量可能不同）。高度为0的建筑物的高度也可以增加。然而，增加的建筑物高度不能影响从任何主要方向观察城市的得到的天际线。

在 不改变 从任何主要方向观测到的城市的天际线的前提下，返回建筑物可以增加的最大高度增量总和。

示例1

输入：grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]] 输出：35 解释：建筑物的高度如上图中心所示。 用红色绘制从不同方向观看得到的天际线。 在不影响天际线的情况下，增加建筑物的高度： gridNew = [ [8, 4, 8, 7], [7, 4, 7, 7], [9, 4, 8, 7], [3, 3, 3, 3] ]

示例2

输入：grid=[[0,0,0],[0,0,0],[0,0,0]] 输出：0 解释：增加任何建筑物的高度都会导致天际线的变化。

方法一：贪心算法

从左侧和右侧看，城市天际线等于矩阵grid每一行的建筑物的最大值；从顶部和底部看，城市天际线等于矩阵grid的每一列的建筑物的最大值。只要不改变每一行和每一列的建筑物的高度的最大值，就能保持城市天际线，因此可以使用贪心的思想计算高度建筑可以增加的最大高度。

由于矩阵grid的行数和列数都是n，因此创建一个两个长度为n的数组rowMax和colMax分别记录建筑物grid的每一行的最大值和每一列的最大值。遍历矩阵grid填入两个数组之后，再次遍历矩阵，计算每个建筑物可以增加的最大值。

对于0<=i, j<n时，对于第i行和第j列的建筑物，其所在行的建筑物高度的最大值是rowMax[i]，其所在列的建筑物的高度的最大值是colMax[j]。为了保持城市天际线，该建筑物增加后的高度不能超过其所在行和所在列的建筑物高度最大值，即该建筑物增加后的最大高度是min(rowMax[i], colMax[j])。由于该建筑物的原始高度是grid[j][j]，因此该建筑物增加后的最大高度是min(rowMax[i], colMax[j]) - grid[i, j].

对于矩阵grid中每个元素可以增加的最大值，即可得到建筑物高度可以增加的最大总和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func maxIncreaseKeepingSkyline(grid [][]int) int {
	//计算每一行的最大值和每一列的最大值
	m, n := len(grid), len(grid[0])
	rowMax := make([]int, m)
	colMax := make([]int, n)
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if rowMax[i] < grid[i][j] {
				rowMax[i] = grid[i][j]
			}
			if colMax[j] < grid[i][j] {
				colMax[j] = grid[i][j]
			}
		}
	}
	// 每一个栅格上的建筑物不能超过所在行最大值、所在列最大值两者的最小值
    // 能增加的最大值是这两者的差
	var ret int
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			ret += min(rowMax[i], colMax[j]) - grid[i][j]
		}
	}
	return ret
}