概要

海側（手前）から順に並んだ建物について、「それまでに見た最大高さ」を更新しながら、海から見える建物（過去の最大より高い建物）の個数を数える問題です。

考察

建物 \(i\) が海から見える条件は、「手前にある建物 \(1 \sim i-1\) の高さの最大値を \(M\) としたとき \(H_i > M\)」です。
これは「過去最高の高さを更新する建物だけが見える」ということを意味します。

重要な観察

• 手前の建物に完全に隠れないためには、少なくともどこかが手前の全ての建物より高くないといけません。
• よって「これまでの最大高さ」を覚えておけば、各建物が見えるかは一発で判定できます。

素朴な方法が遅い理由

各 \(i\) について毎回 \(H_1 \sim H_{i-1}\) の最大値を取り直すと、

• 建物ごとに最大を探すのに \(O(i)\)
• 全体で \(O(1+2+\cdots+N)=O(N^2)\)
  となり、\(N \le 2 \times 10^5\) では間に合いません。

解決策

左から順に見ていき、変数 max_h に「ここまでの最大高さ」を保持します。

• \(H_i > max_h\) なら見える → カウントして max_h を更新
• そうでなければ見えない

例えば \(H=[3,2,5,5,4,6]\) のとき、

• 3（最大更新）→見える
• 2（最大3以下）→見えない
• 5（最大更新）→見える
• 5（最大5以下、等しい）→見えない（条件は \(>\)）
• 4（最大5以下）→見えない
• 6（最大更新）→見える
  よって 3 棟が見えます。

アルゴリズム

1. max_h = -1, cnt = 0 を用意する
2. 建物を \(1\) から \(N\) まで順に見る
3. 高さ \(x=H_i\) について
   • もし \(x > max_h\) なら cnt += 1 し、max_h = x に更新
4. 最後に cnt を出力する

これは「前から見たときの prefix maximum（先頭からの最大値）」を更新していく処理です。

計算量

• 時間計算量: \(O(N)\)（各建物を1回ずつ見るだけ）
• 空間計算量: \(O(1)\)（最大値とカウントだけ。※入力配列を除く）

実装のポイント

• 条件は \(H_i \ge M\) ではなく \(H_i > M\) です（同じ高さだと完全に隠れる扱い）。
• 入力が大きいので、Pythonでは sys.stdin.buffer.read() を使うと高速に読めます。

ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    h = list(map(int, data[1:1+n]))

    max_h = -1
    cnt = 0
    for x in h:
        if x > max_h:
            cnt += 1
            max_h = x
    print(cnt)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。