Pythonで有効な山型配列（Mountain Array）を判定する方法

整数の配列 A が与えられたとき、それが有効な山型配列（Valid Mountain Array）であるかどうかを判定する問題を考えてみましょう。

配列 A が山型配列であるためには、次の条件をすべて満たす必要があります。

山型配列の定義

• 配列 A の長さは 3 以上であること
• あるインデックス i が存在し、以下の2つの条件を満たすこと
  • A[0] < A[1] < ... < A[i-1] < A[i]（山頂まで単調増加）
  • A[i] > A[i+1] > ... > A[A.length - 1]（山頂から単調減少）

つまり、配列が一度も増加せずに減少するだけ、あるいは減少後に再び増加するような場合は山型配列とはみなされません。

たとえば、入力が [0,3,2,1] の場合、0 → 3 と増加した後、3 → 2 → 1 と減少しているため、出力は True になります。

解法のアプローチ

この問題は、配列を先頭から順に走査しながら「増加フェーズ」と「減少フェーズ」をチェックすることで解けます。具体的な手順は以下の通りです。

1. 配列 A のサイズが 3 未満の場合は False を返す
2. i = 1 で初期化する
3. i が配列の範囲内で、かつ A[i] > A[i-1] である限り、i を増やし続ける（増加フェーズ）
4. i が 1 のまま（最初から増加していない）、または i が配列の末尾に達している（減少部分が存在しない）場合は False を返す
5. i が配列の範囲内で、かつ A[i] < A[i-1] である限り、i を増やし続ける（減少フェーズ）
6. i が配列の末尾に到達していれば True、そうでなければ False を返す

Pythonでの実装例

class Solution:
    def validMountainArray(self, A):
        if(len(A)<3):
            return False
        i = 1
        while(i<len(A) and A[i]>A[i-1]):
            i+=1
        if(i==1 or i==len(A)):
            return False
        while(i<len(A) and A[i]<A[i-1]):
            i+=1
        return i==len(A)
ob = Solution()
print(ob.validMountainArray([0,3,2,1]))

入力

[0,3,2,1]

出力

True

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) となります。非常に効率的な解法です。