807. 保持城市天际线

exiaohu 于 2021-12-13 发布

题目链接:807. 保持城市天际线

对每个建筑物而言,能增加的最大高度,是其横向和纵向能增加的最大高度的较小值,而,横向或纵向,最终每个建筑物都可以增加到该方向建筑物高度的最大值。

import heapq
from typing import List


class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        x_sum, y_sum = list(map(max, grid)), list(map(max, zip(*grid)))

        q, ans = [], 0
        for i, row in enumerate(grid):
            for j, height in enumerate(row):
                heapq.heappush(q, (-height, i, j))

        while len(q) > 0:
            h, i, j = heapq.heappop(q)
            ans += min(x_sum[i], y_sum[j]) + h

        return ans