题目链接: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