JavaScriptで条件を満たすタプル(i, j)の最大インデックス差を求める方法

問題

整数の配列 arr を第一引数（唯一の引数）として受け取る JavaScript 関数を作成する必要があります。

配列内の2つのインデックス i と j が、次の条件を満たしているものとします。

• i < j であること
• arr[i] <= arr[j] であること

この条件を満たすすべてのインデックスの組（タプル）(i, j) のうち、差 j - i が最大になるものを見つけ、その値を返します。

たとえば、関数への入力が次の場合：

const arr = [6, 0, 8, 2, 1, 5];

出力は次のようになります。

const output = 4;

出力の解説

最大の差が得られるのは (i, j) = (1, 5) のときです。このとき arr[1] = 0、arr[5] = 5 であり、「i < j」かつ「arr[i] <= arr[j]」の両方の条件を満たし、差は 5 − 1 = 4 となります。

解法：単調スタックを使ったアプローチ

すべての組み合わせを総当たりで調べると計算量は O(n²) になりますが、スタックを活用すれば O(n) まで削減できます。考え方は次のとおりです。

• 左側の候補を収集： 配列を左から走査し、「それまでに出てきた候補よりも小さい値」を持つインデックスだけをスタックに積みます。こうすることで単調減少する候補リストができあがります。ある要素が既存の候補より大きい場合、それは決してより良い答えにならないため、除外できるのがポイントです。
• 右側から照合： 配列を右から走査し、現在の要素 arr[i] がスタックトップの値以上である間、スタックをポップしながら「i − スタックトップのインデックス」を計算して最大値を更新します。右から調べることで、各候補に対して最も遠い（差が最大の）j を確実に見つけられます。

コード例

const arr = [6, 0, 8, 2, 1, 5];
const maximumDifference = (arr = []) => {
    let max = 0
    const stack = [0]
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < arr[stack[stack.length - 1]]) {
            stack.push(i)
        }
    }
    for (let i = arr.length - 1; i >= 0; i--) {
        while (arr[i] >= arr[stack[stack.length - 1]]) {
            max = Math.max(max, i - stack.pop())
        }
    }
    return max;
};
console.log(maximumDifference(arr));

出力結果

コンソールには次のように表示されます。

4

計算量について

時間計算量・空間計算量はともに O(n) であり、要素数の多い配列でも効率的に動作します。二重ループによる総当たり方式（O(n²)）と比べ、パフォーマンス面で大きな優位性があります。