概要

海から建物を順番に見ていき、これまでで最も高い建物よりも高い建物が現れるたびに「見える建物」が増えるので、その個数を数える問題です。

考察

この問題では、建物が海側（左側）から順番に並んでおり、それぞれの建物が「それ以前の建物のどれよりも高くない限り見えない」という条件があります。
つまり、建物 \(i\) が見えるかどうかは、それより手前の建物の中で最も高いものの高さ \(M\) と比較して、\(H_i > M\) であるかどうかで決まります。

したがって、左から順に見ていきながら「これまでの最大の高さ」を記録しておけば、各建物が見えるかどうかを効率的に判定できます。

素朴な方法として、「各建物に対して、それより手前の建物全ての中での最大値を毎回求める」というやり方がありますが、これは各建物について最大 \(N\) 回の比較が必要になり、全体で \(O(N^2)\) の計算量となり、制約 \(N \leq 2 \times 10^5\) では間に合いません（TLEになります）。

そこで、「これまでの最大の高さ」を1つだけ保持しておくという工夫により、各建物に対して定数時間で判定できるようになり、全体で \(O(N)\) で解くことができます。

例えば入力が 2 3 1 4 2 の場合：

• 建物1（高さ2）：最初なので見える。カウント1。最大値を2に更新。
• 建物2（高さ3）：3 > 2 → 見える。カウント2。最大値を3に更新。
• 建物3（高さ1）：1 ≤ 3 → 見えない。
• 建物4（高さ4）：4 > 3 → 見える。カウント3。最大値を4に更新。
• 建物5（高さ2）：2 ≤ 4 → 見えない。

結果として、見える建物の数は3になります。

アルゴリズム

1. 入力から建物の数 \(N\) と各建物の高さのリストを受け取る。
2. 変数 count（見える建物の数）と max_height（これまでの最大の高さ）を初期化する。
3. 左から順に各建物の高さを見ていく：
   • 現在の建物の高さが max_height より大きければ、見えるので count を1増やす。
   • 同時に max_height を現在の建物の高さに更新する。
4. 最後に count を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\) （入力の配列分）

実装のポイント

• 「これまでの最大の高さ」を毎回更新することを忘れないこと。
• 最初の建物（インデックス0）は必ず見えるので、max_height の初期値を0にしておくと自然に処理できる。

ソースコード

n = int(input())
heights = list(map(int, input().split()))

count = 0
max_height = 0

for height in heights:
    if height > max_height:
        count += 1
        max_height = height

print(count)

この解説は qwen3-coder-480b によって生成されました。