概要

全ての山の中で標高が ただ1つだけ最大（狭義最大） になっている山が存在するかを判定し、存在すればその標高、存在しなければ \(0\) を出力します。

考察

「独立峰」とは、他の全ての山よりも標高が高い山です。つまり、

• 最大値が 1回だけ 出現するなら、その最大値の山が独立峰
• 最大値が 2回以上 出現するなら、どの山も「他より厳密に高い（\(>\)）」を満たせないので独立峰は存在しない

ということになります。

例えば標高が \([3, 7, 5]\) なら最大値 \(7\) は1回だけなので答えは \(7\)。
一方 \([3, 7, 7, 5]\) のように最大値 \(7\) が複数回あると、どちらの \(7\) ももう片方の \(7\) より大きくないため独立峰は存在せず答えは \(0\) です。

素朴に「各山 \(i\) について他の全て \(j\) と比較する」と \(O(N^2)\) になり、\(N \le 10^6\) では到底間に合いません。
必要なのは「最大値」と「その出現回数」だけなので、配列を1回走査する \(O(N)\) で解けます。

アルゴリズム

1. 変数 mx を「これまでの最大標高」、cnt を「最大標高の出現回数」とする。
2. 各 \(A_i\) を順に読みながら：
   • \(A_i > mx\) なら mx = A_i、cnt = 1（最大値が更新されたので回数はリセット）
   • \(A_i == mx\) なら cnt += 1（最大値がもう1つ増えた）
3. 最後に cnt == 1 なら答えは mx、そうでなければ \(0\) を出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力全体を保持しない考え方では定数量。※実装では高速化のため入力をバッファ読み込みしています）

実装のポイント

• \(N\) が最大 \(10^6\) と大きいので、Pythonでは input() を繰り返すより、sys.stdin.buffer.read() でまとめて読み、整数を高速にパースすると安定して高速です。

• 判定に必要なのは「最大値」と「最大値の個数」だけなので、配列を保持せずに逐次処理できます（メモリ節約にも有効）。

• cnt == 1 のときだけ最大値を出す、という条件が「狭義最大（\(>\)）」に対応しています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read()
    l = len(data)
    i = 0

    def next_int():
        nonlocal i
        while i < l and data[i] <= 32:
            i += 1
        num = 0
        while i < l and data[i] > 32:
            num = num * 10 + (data[i] - 48)
            i += 1
        return num

    n = next_int()
    mx = -1
    cnt = 0
    for _ in range(n):
        a = next_int()
        if a > mx:
            mx = a
            cnt = 1
        elif a == mx:
            cnt += 1

    sys.stdout.write(str(mx if cnt == 1 else 0))

if __name__ == "__main__":
    main()

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