保持城市天际线

难度: Medium

给你一座由 n x n 个街区组成的城市，每个街区都包含一座立方体建筑。给你一个下标从 0 开始的 n x n 整数矩阵 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
解释：增加任何建筑物的高度都会导致天际线的变化。

提示：

n == grid.length
n == grid[r].length
2 <= n <= 50
0 <= grid[r][c] <= 100

Submission

运行时间: 25 ms

内存: 16.0 MB

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        ans = 0
        list1 = []
        for i in range(len(grid[0])):
            num = -inf
            for li in grid:
                num = max(num, li[i])
            list1.append(num)
        for li in grid:
            n = max(li)
            for i in range(len(li)):
                if li[i] < list1[i] and li[i] < n:
                    if list1[i] <= n:
                        ans += list1[i] - li[i]
                    else:
                        ans += n - li[i]
        return ans

Explain

该题解的思路是分别从行和列的角度计算天际线的高度限制。首先遍历每一列，找出每列的最大高度，存入list1数组。然后遍历grid中的每一行，找出该行的最大高度n。再次遍历该行的每个元素，如果当前元素高度li[i]小于该列限制高度list1[i]且小于该行限制高度n，就可以将当前元素增加到min(list1[i], n)的高度。最后将所有可以增加的高度累加起来即为答案。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        ans = 0
        list1 = []
        # 找出每一列的最大高度
        for i in range(len(grid[0])):
            num = -inf
            for li in grid:
                num = max(num, li[i])
            list1.append(num)
        # 遍历每一行
        for li in grid:
            n = max(li)  # 该行的最大高度
            # 遍历该行的每个元素
            for i in range(len(li)):
                # 如果当前元素高度小于该列限制高度且小于该行限制高度
                if li[i] < list1[i] and li[i] < n:
                    if list1[i] <= n:
                        ans += list1[i] - li[i]  # 增加到列限制高度
                    else:
                        ans += n - li[i]  # 增加到行限制高度
        return ans

Explore

代码实现中虽然没有直接使用min函数来获取list1[i]和n的最小值，但通过if-else结构实现了同样的效果。具体来说，代码通过比较list1[i]和n的大小，然后对li[i]增加到较小的那个值的高度，这与题解描述的增加到min(list1[i], n)的高度是一致的。因此，实现正确反映了题目意图。

题目要求是保持城市的天际线，在这个场景下，天际线是从不同方向（南北和东西）观察建筑物时看到的轮廓线。因此，需要分别计算每一列和每一行的最大高度。每一列的最大值决定了从南向北或从北向南看到的天际线，而每一行的最大值则决定了从东向西或从西向东看到的天际线。因此，需要分别处理列和行的最大值，以确保从任何方向看城市的天际线都不会改变。

现有的遍历方式已经是较优的方法，因为它分别只遍历了一次每列和每行，以获取所需的最大值，并再次遍历整个网格以更新高度并计算增加的总高度。虽然遍历次数是固定的，但考虑到每次遍历都是必须的，以获取必要的数据（列和行的最大值），并且每个单元只被修改一次，这种方法在效率上已经是优化的。要进一步优化，可能需要考虑使用更高效的数据结构或者并行处理，但对于现有的问题规模，这种遍历方法已经足够高效。

这种条件判断完全覆盖了题目的要求。题目的目标是能够增加建筑的高度但不改变天际线。因此，对于每个建筑格，只有当它的高度小于其所在列和行的最大高度时，才考虑增加高度。这里的条件确保了只有在当前建筑的高度既小于列的最大高度也小于行的最大高度时，才对其高度进行调整，这样可以确保增高后不会影响原有的天际线。因此，这种条件判断既没有遗漏也没有冗余，完全符合题目要求。