Pythonで数値リストの方向転換（傾きの変化）回数を求める方法

問題概要

nums という数値のリストが与えられたとき、隣り合う要素間の傾きが「正から負」または「負から正」へと切り替わる回数（方向転換の回数）を求めることを考えます。

例えば、入力が [2, 4, 10, 18, 6, 11, 13] の場合、出力は 2 になります。これは、10 の位置で増加から減少へ（正から負へ）、その後 6 の位置で減少から増加へ（負から正へ）と方向が変わるためです。

解法のアプローチ

この問題は、リストの各要素が「山」（極大値）または「谷」（極小値）に該当するかどうかを順番に調べることで解決できます。手順は以下の通りです。

• インデックス i を 1 から nums の長さ - 2 まで順に走査します。
• nums[i-1] < nums[i] > nums[i+1]（山の形）または nums[i-1] > nums[i] < nums[i+1]（谷の形）を満たす場合、カウント count を 1 増やします。
• ループ終了後、count を返します。

実装例

理解を深めるために、以下の実装を見てみましょう。

class Solution:
    def solve(self, nums):
        count = 0
        for i in range(1, len(nums) - 1):
            if nums[i - 1] < nums[i] > nums[i + 1] or nums[i - 1] > nums[i] < nums[i + 1]:
                count += 1
        return count

ob = Solution()
print(ob.solve([2, 4, 10, 18, 6, 11, 13]))

入力

[2, 4, 10, 18, 6, 11, 13]

出力

2

計算量について

このアルゴリズムはリストを一度だけ走査するため、時間計算量は O(n) であり、追加のメモリも定数 O(1) で済む非常に効率的な方法です。等しい値が連続する場合（平坦な区間）は方向転換とみなさない点にも注意してください。