JavaScriptで「次に大きい要素までの距離」を求めるアルゴリズム

問題概要

数値の配列 arr を唯一の引数として受け取るJavaScript関数を作成します。

この関数の役割は、入力配列をもとに新しい配列を構築することです。新しい配列の各要素には、「現在の要素よりも大きい要素が右側に現れるまでの距離」（インデックスの差）を格納します。もし現在の要素より大きい要素が右側に存在しない場合は、対応する位置に 0 を入れます。最後に、この結果配列を返します。

入力例

const arr = [12, 13, 14, 11, 16, 10, 12, 17, 19, 18];

出力例

const output = [1, 1, 2, 1, 3, 1, 1, 1, 0, 0];

出力の解説

• 12 の次に大きい要素は 13 で、距離は 1
• 13 の次に大きい要素は 14 で、距離は 1
• 14 の次に大きい要素は 16 で、距離は 2（以降も同様）
• 19 および 18 より大きい要素は右側に存在しないため、それぞれ 0 となります

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

この問題は「単調スタック（Monotonic Stack）」というテクニックを使うと効率的に解けます。各要素のインデックスをスタックに保持し、それより大きい要素が現れたタイミングで、スタック内の小さい要素たちの答えをまとめて確定させる仕組みです。

コード例

const arr = [12, 13, 14, 11, 16, 10, 12, 17, 19, 18];

const findNextGreater = (arr = []) => {
    const stack = []
    const res = new Array(arr.length).fill(0)
    for (let i = 0; i < arr.length; i++) {
        while (arr[i] > arr[stack[stack.length - 1]] && stack.length > 0) {
            const index = stack.pop()
            res[index] = i - index
        }
        stack.push(i)
    };
    return res
};

console.log(findNextGreater(arr));

出力

[1, 1, 2, 1, 3, 1, 1, 1, 0, 0]

アルゴリズムのポイント

• 時間計算量：O(n)
  各インデックスは最大でも1回プッシュされ、1回ポップされるだけです。二重ループに見えますが、実際の処理回数は要素数に比例するため、線形時間で完了します。
• 空間計算量：O(n)
  結果配列とスタックのために追加のメモリが必要です。
• 0での初期化が鍵
  結果配列をあらかじめすべて 0 で埋めておくことで、「右側により大きい要素が存在しない」ケースを特別な処理なしに自然に扱うことができます。