0807. Max Increase to Keep City Skyline¶
题目信息¶
- 题号:
0807
- 难度:
Medium
- 主题:
矩阵、行列最大值、城市天际线
- 原题:
- 重点:
每栋建筑只能增高;从上下方向观察的列最大值和从左右方向观察的行最大值都必须保持不变
题目重述¶
给定一个 n x n 整数矩阵 grid,其中 grid[r][c] 表示对应位置建筑的高度。从城市的上方或下方观察时,每一列可见的最高建筑构成列天际线;从左侧或右侧观察时,每一行可见的最高建筑构成行天际线。
可以把任意建筑增加任意非负高度,但增高后四个方向看到的所有行、列最大高度都必须与原来相同。请返回所有建筑高度增加量之和能够达到的最大值。
2 <= n <= 50,0 <= grid[r][c] <= 100。
自建示例¶
同时受所在行和所在列限制:
输入:grid = [[3,0],[2,4]]
输出:4
解释:右上建筑最多从 0 增到 3,左下建筑最多从 2 增到 3,其余两栋不能增高;总增加量为 3 + 1 = 4。
所有建筑都已达到可允许高度:
输入:grid = [[4,4],[4,4]]
输出:0
解释:每行和每列的天际线高度都是 4。任意一栋建筑只要继续增高,就会改变对应行和列的天际线,因此最大总增加量为 0。