概要

手前から奥に向かって並んだ山の中で、今見ている山よりも手前にある山すべてよりも高い山だけが見える。見える山の番号を手前から順に出力する問題。

考察

この問題では、「ある山が見えるかどうか」は、それより手前にあるすべての山の標高が自分より低い場合に限られます。言い換えれば、それまでの山のうち最大の標高よりも高い山だけが新たに見えるということになります。

例えば、山の標高が [2, 1, 4, 3, 5] の場合： - 1番目の山（標高2）は最初なので見える。 - 2番目（標高1）は1番目より低いため見えない。 - 3番目（標高4）はこれまでの最大標高（2）より高いので見える。 - 4番目（標高3）は最大標高（4）より低いので見えない。 - 5番目（標高5）は最大標高（4）より高いので見える。

このように、各山について「これまでの最大標高」を管理しながら順番にチェックすれば良いことがわかります。

素朴な方法として、「各山に対して、それより手前のすべての山を調べる」ような二重ループを考えると、最悪の場合 \(O(N^2)\) となり、\(N\) が最大 \(2 \times 10^5\) なので時間内に処理できません（TLE）。そこで、「これまでの最大標高」を変数で持っておけば、各山について定数時間で判定できるようになり、全体で \(O(N)\) で解けます。

アルゴリズム

1. 入力から山の数 \(N\) と標高リスト \(H\) を受け取る。
2. 「これまでの最大標高」を記録する変数 max_height を -1 で初期化する（標高は正の数なので、最初の山は必ず見える）。
3. 各山 \(i\)（0-indexed）について以下を行う：
   • もし h[i] > max_height なら、その山は見えるので答えに追加し、max_height を更新する。
4. 最後に見える山の番号をスペース区切りで出力する（1-indexedにするために i + 1 を使う）。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力分を除く）

実装のポイント

• 番号は1-indexedで出力する必要があるため、リストのインデックス（0-indexed）に1を足す。
• 最初の山は無条件で見えることに注意。
• max_height は最初 -1 にしておくことで、最初の山も自然に処理できる。

## ソースコード

```python
n = int(input())
h = list(map(int, input().split()))

visible_mountains = []
max_height = -1

for i in range(n):
    if h[i] > max_height:
        visible_mountains.append(i + 1)
        max_height = h[i]

print(' '.join(map(str, visible_mountains)))

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