Pythonで都市のスカイラインを維持したまま建物の高さを最大化する方法

2次元配列 grid があり、grid[i][j] の値はその位置に存在する建物の高さを表しています。任意の数の建物の高さを、任意の量だけ増やすことができます（高さ0も建物として扱います）。ただし重要な制約として、グリッドを上下左右の4方向から見たときの「スカイライン」は、元のグリッドのスカイラインと同一でなければなりません。都市のスカイラインとは、遠くから見たときにすべての建物が形成する長方形の外側の輪郭のことです。この条件下で、建物の高さを増やせる合計の最大値を求める必要があります。

問題の例

例えば、入力が次のようなグリッドだったとします。

この場合の出力は 35 になります。上または下から見たスカイラインは [9, 4, 8, 7]、左または右から見たスカイラインは [8, 7, 9, 3] です。これらの輪郭を維持したまま高さを増やした結果の行列は、次のようになります。

解法のアプローチ

この問題の鍵となるのは、「各セルの高さは、そのセルが属する行の最大値と列の最大値のうち小さい方を超えられない」という性質です。行の最大値を超えると左右方向から見たスカイラインが変わり、列の最大値を超えると上下方向から見たスカイラインが変わってしまうためです。

具体的な手順は以下の通りです。

• 各行の最大値を格納するリスト max_row_wise を作成します。
• 各列の最大値を格納するリスト max_column_wise を作成します。
• 各セル (i, j) について、到達可能な高さの上限 min(top_bottom[i], left_right[j]) を計算し、現在の高さとの差分を合計します。
• すべてのセルの差分の合計が答えとなります。

Pythonでの実装例

それでは、実際のコードを見て理解を深めましょう。

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,3,6],[0,3,1,0]]))

入力

[[3,0,8,4],[2,4,5,7],[9,2,3,6],[0,3,1,0]]

出力

35

補足： より簡潔な書き方

Pythonでは zip(*grid) を使うことで行列を転置できるため、列ごとの最大値もシンプルに取得できます。計算量はどちらの実装でも時間 O(n²)、空間 O(n) ですが、内包表記を使うとコードを大幅に短縮できます。

def maxIncreaseKeepingSkyline(self, grid):
    row_max = list(map(max, grid))
    col_max = list(map(max, zip(*grid)))
    return sum(min(r, c) for r in row_max for c in col_max) - sum(map(sum, grid))