题目描述

[EN | CN]

在二维数组 grid 中,grid[i][j] 代表位于某处的建筑物的高度。 我们被允许增加任何数量(不同建筑物的数量可能不同)的建筑物的高度。 高度 0 也被认为是建筑物。

最后,从新数组的所有四个方向(即顶部,底部,左侧和右侧)观看的“天际线”必须与原始数组的天际线相同。 城市的天际线是从远处观看时,由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。

建筑物高度可以增加的最大总和是多少?

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
例子:
输入: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出: 35
解释:
The grid is:
[ [3, 0, 8, 4],
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

从数组竖直方向(即顶部,底部)看“天际线”是:[9, 4, 8, 7]
从水平水平方向(即左侧,右侧)看“天际线”是:[8, 7, 9, 3]

在不影响天际线的情况下对建筑物进行增高后,新数组如下:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]

说明:

  • 1 < grid.length = grid[0].length <= 50。
  • grid[i][j] 的高度范围是:[0, 100]
  • 一座建筑物占据一个 grid[i][j]:换言之,它们是 1 x 1 x grid[i][j] 的长方体。

解法 1:直接法

首先要理解题目的含义,题目的意思是在「天际线」不能变的前提下尽可能提升各个建筑的高度,而天际线的定义是从上下左右四个方向观看城市建筑时所能看到的最高的高度(类似地平线?)。

因此解题思路就是把每个建筑尽可能地提高但是不超过该行该列的最高建筑。最终要返回的是能够提升的高度,那么我们可以算出来最终的 grid,算所有高度的和,减去原始 grid 所有高度的和。

复杂度分析略。

实现与结果如下:

1
2
3
4
5
6
7
8
9
class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        max_height_of_rows = [max(row) for row in grid]
        max_height_of_cols = [max(col) for col in zip(*grid)]
        return sum(
            min(i, j)
            for i in max_height_of_rows
            for j in max_height_of_cols
        ) - sum(map(sum, grid))
  • 执行用时:92 ms,在所有 Python3 提交中击败了 64.29% 的用户。
  • 内存消耗:13.9 MB,在所有 Python3 提交中击败了 50.00% 的用户。