数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 保持城市天际线最大增量
假设我们有一个名为grid的二维数组，其中grid[i][j]的每个值代表位于该位置建筑物的高度。我们可以通过任意数量来增加任意数量建筑物的高度。高度0也被认为是建筑物。最后，从网格的四个方向观察到的“天际线”必须与原始网格的天际线相同。因为城市的天际线是从远处观察到的所有建筑物形成的矩形的外部轮廓。所以我们必须找到建筑物高度可以增加的最大总和。
因此，如果输入如下：
| 3 | 0 | 8 | 4 |
| 2 | 4 | 5 | 7 |
| 9 | 2 | 3 | 6 |
| 0 | 3 | 1 | 0 |
那么输出将是35，这是因为从顶部或底部观察到的天际线是：[9, 4, 8, 7]，从左侧或右侧观察到的天际线是：[8, 7, 9, 3]，所以最终矩阵可以是这样的：
| 8 | 4 | 8 | 7 |
| 7 | 4 | 7 | 7 |
| 9 | 4 | 8 | 7 |
| 3 | 3 | 3 | 3 |
为了解决这个问题，我们将遵循以下步骤：
max_row_wise := 新列表
max_column_wise := 新列表
counter := 0
对于grid中的每个i，执行：
将i的最大值插入max_row_wise的末尾
counter := counter + 1
counter := 0, i := 0, j := 0
temp_list := 新列表
无限循环执行以下操作：
将grid[i,j]插入temp_list
i := i + 1
如果j等于grid[0]的大小 - 1并且i >= len(grid)，则：
将temp_list的最大值插入max_column_wise的末尾
退出循环
否则，当i >= grid的大小时，则：
i := 0, j := j + 1
将temp_list的最大值插入max_column_wise的末尾
counter := counter + 1
temp_list:= 新列表
top_bottom, left_right := max_row_wise, max_column_wise
i, j, value := 0, 0, 0
无限循环执行以下操作：
temp := [top_bottom[i], left_right[j]] 的最小值
j := j + 1
如果j等于grid的列长度并且i等于grid的行数 - 1，则：
退出循环
否则，当j等于grid的列大小时，则：
i := i + 1
j := 0
返回value
示例
让我们看看下面的实现来更好地理解：
class Solution: def maxIncreaseKeepingSkyline(self, grid): max_row_wise = [] max_column_wise = [] counter = 0 for i in grid: max_row_wise.append(max(i)) counter+=1 counter = 0 i = 0 j = 0 temp_list = [] while True: temp_list.append(grid[i][j]) i+=1 if j ==len(grid[0])-1 and i>=len(grid): max_column_wise.append(max(temp_list)) break elif i >= len(grid): i = 0 j = j + 1 max_column_wise.append(max(temp_list)) counter +=1 temp_list=[] top_bottom, left_right = max_row_wise,max_column_wise i, j, value = 0,0,0 while True: temp = min([top_bottom[i], left_right[j]]) value+= abs(grid[i][j] - temp) j+=1 if j == len(grid[0]) and i==len(grid)-1: break elif j == len(grid[0]): i = i+1 j = 0 return value ob = Solution() print(ob.maxIncreaseKeepingSkyline([[3,0,8,4],[2,4,5,7],[9,2,6,3],[0, 3,1,0]]))
输入
[[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
输出
35
214 次浏览
