C++で配列内の局所的な極値（極大値・極小値）を数える方法

要素数 n の配列 A が与えられたとします。配列の要素 A[i] が、両隣の要素（A[i-1] と A[i+1]）のどちらよりも厳密に小さい場合、その要素は「局所的な極小値（local minimum）」と呼ばれます。逆に、両隣のどちらよりも厳密に大きい場合は「局所的な極大値（local maximum）」となります。

なお、配列の先頭要素 A[0] と末尾要素 A[n-1] は隣接要素が1つしか存在しないため、極大値にも極小値にもなりません。この記事では、与えられた配列に含まれる局所的な極値（極大値と極小値の合計）の個数を求める方法を解説します。

具体例

例として、入力が A = [1, 5, 2, 5] の場合を考えてみましょう。このとき出力は 2 となります。理由は以下の通りです。

• A[1] の値 5 は、隣接する 1 と 2 のどちらよりも大きいため局所的な極大値
• A[2] の値 2 は、隣接する 5 と 5 のどちらよりも小さいため局所的な極小値

アルゴリズムの手順

この問題を解くためには、以下の手順に従います。

1. カウンタ sum を 0 で初期化します。
2. 配列 A のサイズを n とします。
3. i を 1 から n - 2 までループさせ、各要素について以下を判定します。
4. A[i] が両隣より小さい、または両隣より大きい場合、sum を 1 増やします。
5. 最後に sum を返します。

擬似コードで表すと次のようになります。

sum := 0
n := size of A
for initialize i := 1, when i < n - 1, update (increase i by 1), do:
    if (A[i] < A[i - 1] and A[i] < A[i + 1]) or (A[i] > A[i + 1] and A[i] > A[i - 1]), then:
        (increase sum by 1)
return sum

C++での実装例

それでは、実際のC++コードを見てみましょう。理解を深めるために、以下の実装例を参照してください。

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A){
    int sum = 0;
    int n = A.size();
    for (int i = 1; i < n - 1; i++)
        if ((A[i] < A[i - 1] && A[i] < A[i + 1]) || (A[i] > A[i + 1] && A[i] > A[i - 1]))
            sum++;
    return sum;
}

int main(){
    vector<int> A = { 1, 5, 2, 5 };
    cout << solve(A) << endl;
}

入力

{ 1, 5, 2, 5 }

出力

2

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加で必要なメモリは O(1) となります。配列のサイズが大きくなっても効率的に動作する、シンプルかつ実用的なアプローチです。