C++で各要素の左側・右側にある最も近い小さい要素の最大差を求める方法

概要

整数の配列が与えられたとき、配列内の各要素について「左側で最も近い小さい要素」と「右側で最も近い小さい要素」を求め、その絶対差の最大値を計算するのが本記事の目的です。

ここで重要なルールとして、ある要素の左側または右側にそれより小さい要素が存在しない場合は、0 をその要素とみなします。例えば、配列の先頭（最も左）の要素には左側に要素が存在しないため、左側の小さい要素は 0 となります。同様に、配列の末尾（最も右）の要素については、右側の小さい要素が 0 として扱われます。

入力例1

arr[] = {3, 2, 9}

出力例1

2

この場合、各要素ごとの結果は以下のようになります。

• 左側の小さい要素 LS[] = {0, 0, 2}
• 右側の小さい要素 RS[] = {2, 0, 0}

最大差は abs(LS[i] - RS[i]) の最大値となり、|2 - 0| = 2 が出力されます。

入力例2

arr[] = {3, 5, 9, 8, 8, 10, 4}

出力例2

4

この場合の詳細は以下の通りです。

• 左側の小さい要素 LS[] = {0, 3, 5, 5, 5, 8, 3}
• 右側の小さい要素 RS[] = {0, 4, 8, 4, 4, 4, 0}

最大差は |8 - 4| = 4 となります。

解法アプローチ

単純な方法：O(n²)

最も単純なアプローチは、各要素について左側と右側それぞれの最も近い小さい要素を線形探索で求め、その差を順次更新していく方法です。この方法では二重ループが必要となるため、時間計算量は O(n²) になります。

効率的な方法：O(n) スタックを活用

より効率的な解法では、スタックを使用して O(n) の時間計算量を実現します。興味深い点は、左側の小さい要素と右側の小さい要素を同じ関数で計算できることです。

入力配列を Array[]、そのサイズを n と仮定し、以下の手順で処理を行います。

ステップ1：左側の小さい要素をすべて求める

• 空のスタック S と配列 LS[] を用意する
• i を 0 から n-1 まで動かしながら、各要素 Array[i] に対して以下を繰り返す
  • S が空でなく、S のトップ要素が Array[i] 以上である間、S からポップする
  • S が空になった場合：Array[i] より小さい先行要素は存在しないので LS[i] = 0
  • そうでない場合：スタックのトップが最も近い小さい要素なので LS[i] = S.top()
  • 最後に Array[i] を S にプッシュする

ステップ2：右側の小さい要素をすべて求める

• まず配列 Array[] を反転する。反転後は「右側の小さい要素」が「左側の小さい要素」と同じ性質を持つため、同じ関数を再利用できる
• 配列 RRS[] を用意し、ステップ1と同じ手順で RRS を埋める（LS の代わりに）

ステップ3：最大差を計算する

• 結果 result を -1 で初期化する
• 各要素 Array[i] について、反転配列における右側の小さい要素は RRS[n-i-1] に格納されているため、result = max(result, |LS[i] - RRS[n-i-1]|) を計算する

C++実装例

// 配列内の各要素に対して、左側と右側の
// 小さい要素の差を求めるC++プログラム
#include<bits/stdc++.h>
using namespace std;

// Array[0..n1-1] の各要素について左側の小さい要素を求め、
// 結果を SE1[0..n1-1] に格納する関数
void leftSmaller(int Array[], int n1, int SE1[]){
    // 空のスタックを作成
    stack<int>S1;
    // すべての配列要素を走査し、
    // 各要素の最も近い小さい要素を計算
    for (int i=0; i<n1; i++){
        // トップ要素が Array[i] 以上である限り、
        // S1 から要素を取り除き続ける
        while (!S1.empty() && S1.top() >= Array[i])
        S1.pop();
        // 現在の要素より小さい要素を格納
        if (!S1.empty())
            SE1[i] = S1.top();
        // スタック内のすべての要素が Array[i] 以上の場合
        else
            SE1[i] = 0;
            // この要素をプッシュ
            S1.push(Array[i]);
    }
}

// 左右の小さい要素間の最大差を返す関数
int findMaxDiff(int Array[], int n1){
    int LS1[n1]; // 左側の小さい要素を格納
    // 各要素の左側の小さい要素を求める
    leftSmaller(Array, n1, LS1);
    // 各要素の右側の小さい要素を求める
    // まず配列を反転して同じ処理を行う
    int RRS1[n1]; // 反転配列での右側の小さい要素を格納
    reverse(Array, Array + n1);
    leftSmaller(Array, n1, RRS1);
    // LS1 と RRS1 間の最大絶対差を求める
    // 反転配列では Array[i] の右側の小さい要素は
    // RRS1[n1-i-1] に格納されている
    int result1 = -1;
    for (int i=0 ; i< n1 ; i++)
    result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i]));
    // LS1 と RRS1 間の最大差を返す
    return result1;
}

// ドライバープログラム
int main(){
    int Array[] = {3, 5, 9, 8, 8, 10, 4};
    int n = sizeof(Array)/sizeof(Array[0]);
    cout << "Maximum diff : "
    << findMaxDiff(Array, n) << endl;
    return 0;
}

実行結果

Maximum diff : 4

まとめ

本アルゴリズムでは、スタックを活用することで各要素の左右の最も近い小さい要素を効率的に求められます。各要素は最大でも一度プッシュされ、一度ポップされるだけなので、全体の時間計算量は O(n)、補助的な空間計算量も O(n) となります。配列を反転して同じ関数を再利用するテクニックにより、コードの重複を避けつつ簡潔な実装を実現している点がポイントです。