在 Python 中最大程度增加以保留城市天际线

假设我们有一个名为 grid 的二维数组，其中 grid[i][j] 的每个值代表位于该处的建筑物的高度。我们可以将任意数量的建筑物的高度增加任意数量。高度 0 也被视为建筑物。最后，从网格的四个方向看时，"天际线"必须与原始网格的天际线相同。因为城市的天际线是从远处看时所有建筑物形成的矩形的外轮廓。因此，我们必须找到建筑物高度可以增加的最大总和。

因此，如果输入如下

则输出将为 35，这是因为天际线从顶部或底部看到的天际线是:[9, 4, 8, 7]，从左侧或右侧看到的天际线是:[8, 7, 9, 3]，因此最终的矩阵可以是 −

为了解决这个问题，我们将遵循以下步骤 −

• max_row_wise := 一个新列表

• max_column_wise := 一个新列表

• counter := 0

• 对于 grid 中的每个 i，执行

  • 在 max_row_wise 的末尾插入 i 的最大值

  • counter := counter + 1

• counter := 0, i := 0, j := 0

• temp_list := a new list

• 无限次执行以下操作 −

  • 将 grid[i,j] 插入 temp_list

  • i := i + 1

  • 如果 j 与 grid[0] -1 的大小相同且 i>=len(grid)，则

    • 在 max_column_wise 的末尾插入 temp_list 的最大值

    • 退出循环

  • 否则，当 i >= 网格大小时，则

    • i := 0, j := j + 1

    • 在 max_column_wise 的末尾插入 temp_list 的最大值

    • 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 与网格的列长度相同且 i 与网格的行数 -1 相同，则

    • 退出循环

  • 否则，当 j 与网格列的大小相同时，则

    • 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

相关文章

• Python - 使用交替的 0 和 1 初始化列表
• Python 中元组列表到字典的转换
• Python - 从两个列表中配对，使得成对的元素不相同
• 使用 Python 和 SQLite 的 SQL
• 使用 pytrie 模块在 Python 中进行前缀匹配
• 创建和访问 Python 包
• 如何使用正则表达式和数据类型选择多个 DataFrame 列
• 如何在 Pandas 中查找和过滤重复行?
• 用 Python 编写程序以正确的顺序查找机场?
• 如何在 Python Pandas 中使用字典顺序切片选择数据子集?

有用资源

• python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/