Pythonで「良い眺め」を持つ建物を見つけるプログラム

高さの異なる建物の高さを格納した配列が与えられているとします。建物は一列に並んでおり、ある建物が「良い眺め」を持つのは、それより高い別の建物によって視界が遮られない場合です。つまり、高さの配列が与えられたとき、他の高い建物に邪魔されずに眺めを楽しめる建物を見つけ出す必要があります。そして、その条件を満たす要素のインデックスを返します。

問題の例

例えば、入力が height = [5, 6, 8, 7] の場合、出力は [2, 3] となります。インデックス0と1の建物は、インデックス2にあるより高い建物に遮られています。一方、インデックス2と3の建物は遮られていません。これは、位置2にある高い建物が、位置3にある低い建物よりも後ろ(右側)に位置しているためです。

解決のためのアプローチ

この問題は、配列を右から左へ(末尾から先頭へ)走査することで効率的に解けます。手順は以下の通りです。

• 結果を格納する空のリスト res と、それまでに見た最大の高さ h(初期値0)を用意します。
• 配列の末尾から先頭に向かって各建物を調べます。
• 現在の建物の高さ heights[i] が h より大きければ、その建物は遮られないため、インデックス i を res に追加し、h を更新します。
• 最後に res を反転して返します。これにより、インデックスが左から右の自然な順序になります。

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) であり、非常に効率的です。

実装例

以下のPythonコードを見て、理解を深めましょう。

def solve(heights):
    res, h = [], 0
    for i in range(len(heights) - 1, -1, -1):
        if heights[i] > h:
            res.append(i)
            h = heights[i]
    return res[::-1]

print(solve([5, 6, 8, 7]))

入力

[5, 6, 8, 7]

出力

[2, 3]