807.保持城市天际线.md

807.保持城市天际线

原题

找到每行和每列的最高高度，即为天际线skyRow，skyCol，对建筑(i,j)，其最高高度为min(skyRow, skyCol)

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        n = len(grid)
        skyRow = [-1] * n
        skyCol = [-1] * n
        # 找每行的天际线
        for i in range(n):
            maxRow = -1
            for j in range(n):
                if grid[i][j] > maxRow:
                    maxRow = grid[i][j]
            skyRow[i] = maxRow
        # 找每列的天际线
        for j in range(n):
            maxCol = -1
            for i in range(n):
                if grid[i][j] > maxCol:
                    maxCol = grid[i][j]
            skyCol[j] = maxCol
        # 遍历矩阵
        cnt = 0
        for i in range(n): 
            for j in range(n):
                cnt += min(skyRow[i], skyCol[j]) - grid[i][j]
        return cnt