Pythonでリストが交互に増加・減少しているかどうかを判定するプログラム

問題の概要

数値のリスト nums が与えられ、それが「厳密に増加 → 厳密に減少 → 厳密に増加 → …」というように、増加と減少が交互に入れ替わっているかどうかを判定します。ただし、リスト全体がずっと厳密に増加し続けている場合も条件を満たすものとみなします。

たとえば入力が [2, 4, 8, 7, 5, 1, 5, 7, 2, 1] の場合、出力は True になります。[2, 4, 8] が増加し、続く [7, 5, 1] が減少、その後の [5, 7] が再び増加、最後の [2, 1] が減少しており、増加と減少がきちんと交互に現れているためです。

解法の考え方

一見すると、増加区間と減少区間を切り分けながら複雑に走査する必要があるように思えますが、実際はもっとシンプルに判定できます。確認すべきポイントは次の2つだけです。

• 最初は必ず増加で始まること：nums[1] <= nums[0] であれば、その時点で条件違反となるため False を返します。
• 隣接する要素が等しくてはならないこと：「厳密な」増加・減少が求められているため、nums[i] == nums[i - 1] となる箇所がひとつでもあれば False を返します。

この2つのチェックを通過したリストは、必ず条件を満たします。隣接要素がすべて異なる数列は「最大の単調区間」（増加のみ、または減少のみが続く区間）に分解できますが、隣り合う単調区間は必ず方向が入れ替わるため、増加と減少は自然に交互に現れるからです。

アルゴリズムの手順

1. nums[1] <= nums[0] ならば False を返す。
2. リストを先頭から順に走査し、隣接する2要素 nums[i] と nums[i - 1] が等しければ False を返す。
3. 最後まで問題がなければ True を返す。

実装例

以下がPythonでの実装例です。

def solve(nums):
    if nums[1] <= nums[0]:
        return False
    for i in range(len(nums)):
        if i - 1 >= 0:
            if nums[i] == nums[i - 1]:
                return False

    return True

nums = [2, 4, 8, 7, 5, 1, 5, 7, 2, 1]
print(solve(nums))

入力

[2, 4, 8, 7, 5, 1, 5, 7, 2, 1]

出力

True

計算量

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

注意点

上記の実装は nums[1] に直接アクセスするため、要素数が1以下のリストを渡すと IndexError が発生します。実務では冒頭に if len(nums) < 2: return True のようなガードを追加しておくと安全です（要素が0個または1個のリストは自明に条件を満たすものとして扱います）。