概要

与えられた山の標高の中から、唯一の最大値（狭義最大）を求める問題。最大値が複数ある場合は \(0\) を出力する。

考察

この問題では、「独立峰」とはすべての山より真に高い山であることを意味しており、つまり最大の標高がただ一つだけ存在する必要がある。

例えば以下のような入力を見てみよう。

例1:

入力:

5
1 3 2 5 4

最大値は \(5\) で、それがただ一つだけ存在するため、答えは \(5\)。

例2:

入力:

5
1 5 2 5 3

最大値は \(5\) だが、それが2つあるため、どの山も「他のすべてより高い」とは言えない。よって答えは \(0\)。

したがって、問題の本質は「最大値が一意かどうか」を判定することである。

素朴なアプローチとして、すべての山について他のすべてと比較する方法（二重ループ）が考えられるが、これは \(N\) が最大で \(10^6\) なので、時間計算量 \(O(N^2)\) となりTLE（Time Limit Exceeded）になる。

しかし、実際には最大値を一度走査で求め、その出現回数を数えるだけで十分である。これにより、計算量を大きく削減できる。

アルゴリズム

1. まず、配列 \(A\) の最大値 \(max\_height\) を求める。
2. 次に、その最大値が配列内に何回出現するかをカウントする。
3. 出現回数がちょうど1回であれば、それが独立峰なのでその値を出力。
4. そうでなければ（つまり2回以上出現すれば）、独立峰は存在しないので \(0\) を出力。

計算量

• 時間計算量: \(O(N)\)
  • 最大値を求める処理と、出現回数をカウントする処理がそれぞれ \(O(N)\)。
• 空間計算量: \(O(N)\)
  • 入力配列 \(A\) を保持するのに \(O(N)\) 必要。

実装のポイント

• max(A) で最大値を取得。

• A.count(max_height) でその最大値の出現回数を取得。

• 出現回数が1かどうかで分岐させる。

  ソースコード

N = int(input())
A = list(map(int, input().split()))

max_height = max(A)
if A.count(max_height) == 1:
    print(max_height)
else:
    print(0)

---

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