JavaScriptでarr[i] <= arr[j]を満たす最大のインデックス差（j - i）を求める方法

問題

数値の配列 arr を受け取るJavaScript関数を作成します。この関数は、arr[i] <= arr[j] を満たす組み合わせの中から、j - i の差が最も大きくなる値を返す必要があります。

つまり、「前方の要素が後方の要素以下である」という条件を満たす、2つのインデックス間の最大距離を求めるという問題です。

解決アプローチ

最もシンプルな方法は、ネストされたループを使ってすべてのインデックスのペア (i, j) を調べることです。各ペアについて arr[i] <= arr[j] が成立するかどうかを確認し、その差 j - i が現在の結果より大きければ更新していきます。

コード例

実装コードは以下のとおりです。

const arr = [1, 2, 3, 4];
const findLargestDifference = (arr = []) => {
    const { length: len } = arr;
    let res = 0;
    for(let i = 0; i < len; i++){
        for(let j = i + 1; j < len; j++){
            if(arr[i] <= arr[j] && (j - i) > res){
                res = j - i;
            };
        };
    };
    return res;
};
console.log(findLargestDifference(arr));

出力結果

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

3

処理の解説

この例では、配列 [1, 2, 3, 4] は昇順に並んでいるため、任意の i < j について arr[i] <= arr[j] が常に成り立ちます。したがって、最大の差は最初のインデックス 0 と最後のインデックス 3 の組み合わせとなり、結果は 3 になります。

なお、この二重ループによるアプローチの計算量は O(n²) です。配列サイズが大きい場合には、単調減少スタックなどを活用した O(n) の効率的なアルゴリズムを検討するとよいでしょう。