資料結構
網路
關係資料庫管理系統 (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 次瀏覽
