C++で配列内の前後の要素よりも大きい要素を見つける方法

問題概要

この問題では、n個の正の整数からなる配列 arr[] が与えられます。求めるのは、配列の中で「直前の要素と直後の要素のどちらよりも大きい」要素を見つけることです。

条件の説明

具体的には、ある要素 arr[i] が次の2つの条件を同時に満たすかどうかを判定します。

• arr[i] > arr[i-1]（1つ前の要素より大きい）
• arr[i] > arr[i+1]（1つ後の要素より大きい）

この両方を満たす要素をすべて出力すればよいわけです。

入出力例で問題を理解する

入力： arr[] = {3, 2, 5, 7, 3, 4, 5}

出力： 7

説明：

要素 7 に注目すると、1つ前の要素は 5、1つ後の要素は 3 です。現在の要素 7 はこの両方よりも大きいため、条件を満たしていることがわかります。

解法アプローチ

最もシンプルな解法は、配列の各要素に対して条件を順番にチェックし、条件を満たす要素を出力するというものです。

手順は以下の通りです。

ステップ1： インデックス 1 から n-2 までループで配列を走査します。

ステップ1.1： 各要素 arr[i] について、arr[i] > arr[i-1] かつ arr[i] > arr[i+1] が成り立つかを判定します。

ステップ1.2： 条件が真であれば、arr[i] を出力します。

なお、配列の先頭と末尾の要素には「前後両方の要素」が存在しないため、チェック対象から除外される点に注意してください。

解法の実装例（C++）

以下は、このアルゴリズムを実装したC++のサンプルプログラムです。

サンプルコード

#include <iostream>
using namespace std;

void findElementsInArray(int arr[], int n) {
    for (int i = 1; i < n-1; i++)
        if ( (arr[i] > arr[i+1] && arr[i] > arr[i-1]) ) {
            cout<<arr[i]<<"\t";
        }
}

int main()
{
    int n = 8;
    int arr[n] = { 5, 4, 7, 1, 17, 8, 3 };
    cout<<"The elements that satisfy the given condition are ";
    findElementsInArray(arr, n);
    return 0;
}

実行結果

The elements that satisfy the given condition are 7 17

このプログラムでは、配列 { 5, 4, 7, 1, 17, 8, 3 } の中で、7 は前後の要素（4 と 1）より大きく、17 も前後の要素（1 と 8）より大きいため、両方が出力されます。

計算量について

この解法は配列を一度だけ走査するため、時間計算量は O(n) です。また、追加のメモリを必要としないため、空間計算量は O(1) となります。要素数が多い配列でも効率的に処理できる、シンプルかつ実用的なアルゴリズムです。