Pythonで都市のスカイラインを維持するための最大増加

gridという2次元配列があるとします。ここで、grid [i] [j]の各値は、そこにある建物の高さを表します。任意の数の建物の高さを任意の量だけ増やすことができます。高さ0も建物と見なされます。最後に、グリッドの4つの方向すべてから見たときの「スカイライン」は、元のグリッドのスカイラインと同じである必要があります。なぜなら、都市のスカイラインは、遠くから見たときにすべての建物によって形成される長方形の外側の輪郭だからです。したがって、建物の高さを増やすことができる最大の合計を見つける必要があります。

したがって、入力が次のような場合

その場合、出力は35になります。これは、上または下から見たスカイラインが[9、4、8、7]であり、左または右から見たスカイラインが[8、7、9、3]であるためです。最終的な行列は次のようになります-

これを解決するには、次の手順に従います-

• max_row_wise：=新しいリスト

• max_column_wise：=新しいリスト

• カウンター：=0

• グリッド内の各iについて、実行します

  • max_row_wiseの最後に最大iを挿入します

  • カウンター：=カウンター+ 1

• カウンター：=0、i：=0、j：=0

• temp_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の最大値を挿入します

    • カウンター：=カウンター+ 1

    • temp_list：=新しいリスト

• top_bottom、left_right：=max_row_wise、max_column_wise

• i、j、値：=0,0,0

• 次のことを無限に行います。

  • temp：=最小[top_bottom [i]、left_right [j]]

  • j：=j + 1

  • jがグリッドの列の長さと同じで、iがグリッド-1の行数と同じである場合、

    • ループから出てきます

  • それ以外の場合、jがグリッド列のサイズと同じである場合、

    • i：=i + 1

    • j：=0

• 戻り値

例

理解を深めるために、次の実装を見てみましょう-

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