JZX轻语：简

LeetCode 807 - 保持城市天际线

发表于2024年05月09日

#贪心 #矩阵

通过观察得知，若需要保持四个方向的天际线不变，本质就是保持每行每列的最大值不变。因此，对于第i行第j列的建筑，其可以将高度扩展到第i行最大值和第j列最大值两者的最小值。

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        n = len(grid)

        row_max = [max(row) for row in grid]
        col_max = [max(grid[i][j] for i in range(n)) for j in range(n)]

        ans = 0
        for i in range(n):
            for j in range(n):
                ans += min(row_max[i], col_max[j]) - grid[i][j]
        return ans

闪念标签：LC

题目链接：https://leetcode.cn/problems/max-increase-to-keep-city-skyline/